diff options
Diffstat (limited to 'chain/src')
| -rw-r--r-- | chain/src/atom/default.rs | 19 | ||||
| -rw-r--r-- | chain/src/default.rs | 82 | ||||
| -rw-r--r-- | chain/src/item/default.rs | 125 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 318 | ||||
| -rw-r--r-- | chain/src/item/mod.rs | 1 | ||||
| -rw-r--r-- | chain/src/plan.org | 6 |
6 files changed, 447 insertions, 104 deletions
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs index e88cfc9..9c91296 100644 --- a/chain/src/atom/default.rs +++ b/chain/src/atom/default.rs @@ -48,18 +48,31 @@ pub struct DefaultAtom { impl DefaultAtom { /// Return the string description of a rule position. pub fn rule_pos_string(&self, pos: usize) -> Result<String, Box<dyn std::error::Error>> { + if pos == self.grammar.total() { + return Ok("End of rules".to_owned()); + } + let rule_num = self.grammar.get_rule_num(pos)?; assert!(rule_num < self.grammar.non_num()); - let display_tnt = |tnt| self.name_of_tnt(tnt).unwrap_or_else(|e| format!("{e}")); + let display_tnt = |tnt| { + format!( + " {} ", + self.name_of_tnt(match tnt { + TNT::Non(_) => tnt, + TNT::Ter(t) => self.unpack_tnt(t).unwrap(), + }) + .unwrap_or_else(|e| format!("{e}")) + ) + }; Ok(self.regexp.get(rule_num).unwrap().to_string_with_dot( display_tnt, if rule_num == 0 { pos } else { - pos - self.grammar.nth_accumulator(rule_num - 1)? + pos - self.grammar.nth_accumulator(rule_num)? }, )?) } @@ -394,8 +407,6 @@ impl DefaultAtom { } } - // dbg!(&accumulators); - for nt in 0..nt_num { let children: std::collections::HashMap<_, _> = nfa // This is safe because of the above assertion. diff --git a/chain/src/default.rs b/chain/src/default.rs index 77a64ca..5e94623 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -8,7 +8,8 @@ use super::*; use crate::atom::{Atom, DefaultAtom}; use crate::item::{ - default::DefaultForest, generate_fragment, Forest, ForestLabel, ForestLabelError, + default::DefaultForest, generate_fragment, genins::virtual_generate_fragment, Forest, + ForestLabel, ForestLabelError, }; use core::fmt::Display; use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT}; @@ -35,6 +36,8 @@ pub enum Error { CannotClone(ForestLabelError), /// Cannot find a suitable node to plant the new forest fragment. CannotPlant, + /// Trying to insert an empty item. + EmptyItem, /// An invalid situation happens. Invalid, } @@ -52,6 +55,7 @@ impl Display for Error { Self::CannotReserve(e) => write!(f, "cannot reserve memory: {e}"), Self::CannotClone(fe) => write!(f, "cannot clone due to {fe}"), Self::CannotPlant => write!(f, "cannot plant a new forest fragment"), + Self::EmptyItem => write!(f, "trying to insert an empty item"), Self::Invalid => write!(f, "invalid"), } } @@ -393,7 +397,6 @@ impl Chain for DefaultChain { .is_nullable(0) .map_err(|_| Error::IndexOutOfBounds(0, atom.non_num()))?; - // NOTE: Is it really correct to use `Parent::new(0, 0)` here? builder.add_edge( first, root, @@ -585,15 +588,13 @@ impl Chain for DefaultChain { )?; } Some(Non(non)) => { - let first_fragment = - generate_fragment([atom_moved.into(), Non(non).into()], pos)?; - - let first_segment_pase = self.forest.insert_item( - *label, - first_fragment, - atom_child_iter.clone(), - &self.atom, - )?; + if !self + .atom + .is_first_of(non, t) + .map_err(index_out_of_bounds_conversion)? + { + continue; + } let virtual_node = self .atom @@ -601,59 +602,30 @@ impl Chain for DefaultChain { .map_err(index_out_of_bounds_conversion)?; if let Some(virtual_node) = virtual_node { + let first_fragment = + generate_fragment([atom_moved.into(), Non(non).into()], pos)?; + + let first_segment_pase = self.forest.insert_item( + *label, + first_fragment, + atom_child_iter.clone(), + &self.atom, + )?; + let accepting = self .atom .is_accepting(virtual_node) .map_err(index_out_of_bounds_conversion)?; - let virtual_fragment = { - // `non` is valid, as checked above - let non_start = self.atom.nth_accumulator(non).unwrap() * 2; - - let mut result = DefaultForest::default(); - - for (label, child_iter) in self.atom.labels_of(non_start)? { - if matches!(*label.get_value(), - Some(Ter(ter)) if ter == t) - { - for child in child_iter { - let mut line: Vec<_> = self - .atom - .query_expansion(non_start, child) - .map_err(index_out_of_bounds_conversion)? - .iter() - .copied() - .flatten() - .map(|(nt, rule)| [(*rule).into(), Non(*nt).into()]) - .collect(); - - line.push([label.get_moved().into(), Ter(t).into()]); - - let line: Vec<GrammarLabelType> = - line.into_iter().flatten().collect(); - - if result.is_empty() { - result = generate_fragment(line, pos)?; - } else { - result.plant( - 0, - generate_fragment(line, pos)?, - false, - )?; - } - } - } - } - - result - }; + let virtual_fragment = + virtual_generate_fragment(&self.atom, non, t, pos)?; // NOTE: We only need the PaSe from the // first segment, so we pass an empty // iterator, in which case the passed // label is only used for the PaSe. let virtual_pase = self.forest.insert_item( - Edge::new(0, first_segment_pase, true), + Edge::new(0, first_segment_pase, accepting), virtual_fragment, std::iter::empty(), &self.atom, @@ -810,8 +782,8 @@ mod test_chain { let atom = DefaultAtom::from_grammar(grammar)?; let mut chain = DefaultChain::unit(atom)?; - chain.chain(3, 00)?; + dbg!("hi"); chain.chain(1, 01)?; chain.chain(2, 02)?; chain.chain(2, 03)?; @@ -831,6 +803,8 @@ mod test_chain { { chain.graph.print_viz("chain.gv")?; chain.atom.print_nfa("nfa.gv")?; + chain.forest.print_viz("forest.gv")?; + item::default::print_labels(&chain.atom, &chain.forest)?; } Ok(()) diff --git a/chain/src/item/default.rs b/chain/src/item/default.rs index b71f940..f9d26ec 100644 --- a/chain/src/item/default.rs +++ b/chain/src/item/default.rs @@ -2,6 +2,8 @@ //! forest. use super::*; +use crate::atom::default::DefaultAtom; +use grammar::{GrammarLabel, GrammarLabelType}; use graph::{ builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, LabelGraph, PLGraph, RedirectGraph, }; @@ -125,6 +127,11 @@ impl<T: GraphLabel> Graph for DefaultForest<T> { fn replace_by_builder(&mut self, _builder: impl graph::Builder<Result = Self>) { unimplemented!() } + + #[inline] + fn print_viz(&self, filename: &str) -> Result<(), std::io::Error> { + self.graph.print_viz(filename) + } } impl<T: GraphLabel> ParentsGraph for DefaultForest<T> { @@ -360,9 +367,18 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { stack.push(root); + let mut seen_nodes = std::collections::HashSet::<usize>::new(); + while let Some(top) = stack.pop() { + seen_nodes.insert(top); + for child in fragment.children_of(top)? { builder.add_edge(conversion!(top), conversion!(child), root_label)?; + + if !seen_nodes.contains(&child) { + seen_nodes.insert(child); + stack.push(child); + } } } @@ -451,22 +467,82 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { } } +impl<T: GraphLabel> PartialEq for DefaultForest<ForestLabel<T>> { + fn eq(&self, other: &Self) -> bool { + let self_root = self.root(); + let other_root = other.root(); + + if (self_root.is_some() && other_root.is_none()) + || (self_root.is_none() && other_root.is_some()) + { + return false; + } else if self_root.is_none() && other_root.is_none() { + return true; + } + + // both roots are not empty + + let self_root = self_root.unwrap(); + let other_root = other_root.unwrap(); + + self.is_prefix(self_root, other).unwrap_or(false) + && other.is_prefix(other_root, self).unwrap_or(false) + } +} + +impl<T: GraphLabel> Eq for DefaultForest<ForestLabel<T>> {} + +/// Print the labels found in the forest, so that we can easily +/// understand what those labels mean. +pub fn print_labels( + atom: impl Borrow<DefaultAtom>, + forest: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>, +) -> Result<(), Box<dyn std::error::Error>> { + let forest = forest.borrow(); + let atom = atom.borrow(); + + for node in forest.nodes() { + let label = forest.vertex_label(node)?; + + if let Some(label) = label { + let label = label.label.label(); + + match label { + GrammarLabelType::TNT(tnt) => { + println!("{tnt} = {}", atom.name_of_tnt(tnt)?); + } + GrammarLabelType::Rule(pos) => { + println!("pos {pos} = {}", atom.rule_pos_string(pos)?); + } + } + } else { + return Err(Error::NodeNoLabel(node).into()); + } + } + + Ok(()) +} + +#[allow(unused_macros)] +macro_rules! leaf ( + ($label:expr, $type:tt) =>{ + DefaultForest::<ForestLabel<$type>>::new_leaf($label) + }; + ($label:expr) => { + DefaultForest::<ForestLabel<usize>>::new_leaf($label) + } +); + +#[allow(unused_imports)] +pub(crate) use leaf; + #[cfg(test)] mod item_test { use super::*; - macro_rules! leaf ( - ($label:expr, $type:tt) =>{ - DefaultForest::<ForestLabel<$type>>::new_leaf($label) - }; - ($label:expr) => { - DefaultForest::<ForestLabel<usize>>::new_leaf($label) - } - ); - #[test] fn test_forest_api() -> Result<(), Box<dyn std::error::Error>> { - let forest: DefaultForest<usize> = Default::default(); + let forest: DefaultForest<ForestLabel<usize>> = Default::default(); // empty forest @@ -537,11 +613,38 @@ mod item_test { forest.clone_node(5)?; - assert_eq!(forest.nodes_len(), 7); + assert_eq!(forest.nodes_len(), 8); #[cfg(feature = "test-print-viz")] forest.print_viz("forest.gv")?; Ok(()) } + + #[test] + fn test_eq() -> Result<(), Box<dyn std::error::Error>> { + let mut forest = leaf!(0, usize); + + forest.plant(0, leaf!(1), false)?; + forest.plant(0, leaf!(2), false)?; + forest.plant(0, leaf!(3), false)?; + forest.plant(0, leaf!(4), false)?; + forest.plant(2, leaf!(5), false)?; + + let mut test_forest = leaf!(0); + test_forest.plant(0, leaf!(1), false)?; + test_forest.plant(0, leaf!(2), false)?; + test_forest.plant(0, leaf!(3), false)?; + test_forest.plant(2, leaf!(5), false)?; + + assert_ne!(forest, test_forest); + assert_ne!(test_forest, forest); + + test_forest.plant(0, leaf!(4), false)?; + + assert_eq!(forest, test_forest); + assert_eq!(test_forest, forest); + + Ok(()) + } } diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 99d9202..9ed3b74 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -14,6 +14,17 @@ use graph::Graph; use core::borrow::Borrow; use std::collections::HashSet as Set; +/// Convert an error telling us that an index is out of bounds. +/// +/// # Panics +/// +/// The function panics if the error is not of the expected kind. +fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { + match ge { + GrammarError::IndexOutOfBounds(index, bound) => Error::IndexOutOfBounds(index, bound), + _ => Error::Invalid, + } +} /// A helper function to generate a fragment of forest. /// /// It simply constructs a root node and then appends @@ -56,6 +67,53 @@ pub fn generate_fragment( Ok(result) } +/// Generate a virtual fragment representing the left-linear null +/// closure [nt]^t. +pub fn virtual_generate_fragment( + atom: impl Borrow<DefaultAtom>, + nt: usize, + t: usize, + pos: usize, +) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, crate::default::Error> { + let atom = atom.borrow(); + + let non_start = atom.nth_accumulator(nt).unwrap() * 2; + + let mut result = DefaultForest::default(); + + for (label, child_iter) in atom.labels_of(non_start)? { + if matches!(*label.get_value(), + Some(TNT::Ter(ter)) if ter == t) + { + for child in child_iter { + // #[allow(unused_must_use)] + // { + // dbg!(non_start, child, atom.query_expansion(non_start, child)); + // } + + let line: Vec<GrammarLabelType> = atom + .query_expansion(non_start, child) + .map_err(index_out_of_bounds_conversion)? + .iter() + .copied() + .flatten() + .flat_map(|(nt, rule)| [(*rule).into(), TNT::Non(*nt).into()]) + .rev() + .chain(std::iter::once(TNT::Ter(t).into())) + .collect(); + + if result.is_empty() { + result = generate_fragment(line, pos)?; + } else { + result.plant(0, generate_fragment(line, pos)?, false)?; + } + } + } + } + + Ok(result) +} + impl DefaultForest<ForestLabel<GrammarLabel>> { /// Insert an item derivation forest into a recording forest. /// @@ -68,26 +126,39 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { atom_child_iter: impl Iterator<Item = usize>, atom: &DefaultAtom, ) -> Result<PaSe, Error> { - /// Convert an error telling us that an index is out of bounds. - /// - /// # Panics - /// - /// The function panics if the error is not of the expected - /// kind. - fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { - match ge { - GrammarError::IndexOutOfBounds(index, bound) => { - Error::IndexOutOfBounds(index, bound) - } - _ => Error::Invalid, - } - } - let fragment = fragment.borrow(); let pase = label.forest_source(); - let parents: Vec<Parent> = { + let _fragment_root = if let Some(root) = fragment.root() { + root + } else { + return Err(Error::EmptyItem); + }; + + // Ensure the last node in the PaSe is a terminal or a + // non-terminal node, as an extra safety guard during + // development. + #[cfg(debug_assertions)] + { + if let Some(parent) = pase.parent() { + assert!(matches!( + self.vertex_label(self.nth_child(parent.node(), parent.edge())?), + Ok(Some(label)) + if label.label().label().tnt().is_some())); + } else if let Some((_, leaf)) = pase.segment() { + assert!(matches!( + self.vertex_label(leaf), + Ok(Some(label)) + if label.label().label().tnt().is_some())); + } else { + unreachable!("a pase is neither a parent nor a segment"); + } + } + + let mut is_empty_segment = false; + + let mut parents: Vec<Parent> = { let mut result = Vec::new(); if let Some(parent) = pase.parent() { @@ -96,7 +167,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let (root, leaf) = pase.segment().unwrap(); let mut seen_nodes = Set::new(); - let mut stack = vec![root]; + let mut stack = if root == leaf { + // an empty segment means the root + is_empty_segment = true; + + result.push(Parent::new(root, 0)); + vec![] + } else { + vec![root] + }; while let Some(top) = stack.pop() { if seen_nodes.contains(&top) { @@ -118,7 +197,35 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { result }; + for parent in parents.iter() { + if !self.has_node(parent.node()) { + return Err(Error::IndexOutOfBounds(parent.node(), self.nodes_len())); + } + } + + if !is_empty_segment { + parents = parents + .into_iter() + .flat_map(|parent| { + self.parents_of(parent.node()).unwrap().filter(|n| { + matches!( + self.vertex_label(n.node()) + .unwrap() + .unwrap() + .label() + .label() + .tnt(), + Some(TNT::Non(_)) + ) + }) + }) + .collect(); + } + + let mut non_empty = false; + for atom_child in atom_child_iter { + // dbg!(label.label(), atom_child); // Find reduction information. let reduction_info = atom .query_reduction(label.label(), atom_child) @@ -142,20 +249,20 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { ) { for parent in self.parents_of(node.node())? { debug_assert!(matches!( - self.vertex_label(parent.node()), - Ok(Some(label)) if - label - .label() - .label() - .rule() - .is_some())); + self.vertex_label(parent.node()), + Ok(Some(label)) if + label + .label() + .label() + .rule() + .is_some())); second_stack.extend(self.parents_of(parent.node())?.filter(|n| { matches!(self.vertex_label(n.node()), - Ok(Some(label)) - if matches!( - label.label().label().tnt(), - Some(TNT::Non(_)))) + Ok(Some(label)) + if matches!( + label.label().label().tnt(), + Some(TNT::Non(_)))) })); } } @@ -169,12 +276,26 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { } if stack.is_empty() { + dbg!( + label, + atom_child, + parents, + reduction_info, + atom.query_reduction(label.label(), atom_child).unwrap() + ); + + self.print_viz("dbg forest.gv").unwrap(); + + #[cfg(test)] + genins_test::print_labels(atom, self).unwrap(); + return Err(Error::CannotPlant); } for parent in stack.into_iter() { if parent.edge() + 1 >= self.degree(parent.node())? { - self.plant(parent.node(), fragment, false)?; + // dbg!(&fragment); + self.plant(parent.node(), fragment, non_empty)?; } else { let nth_child = self.nth_child(parent.node(), parent.edge() + 1)?; @@ -182,11 +303,26 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // do nothing continue; } + dbg!("clone?"); let cloned_node = self.clone_node(nth_child)?; - self.plant(cloned_node, fragment, false)?; + self.plant(cloned_node, fragment, non_empty)?; } + + non_empty = true; + } + } + + // If the iterator is empty, just plant at the specified + // child. + if !non_empty { + for parent in parents.into_iter() { + let nth_child = self.nth_child(parent.node(), parent.edge())?; + + self.plant(nth_child, fragment, non_empty)?; + + non_empty = true; } } @@ -214,11 +350,12 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { unreachable!("the forest is wrongly planted"); } }; - + // dbg!(node, edge, root_label, leaf_label); PaSe::Parent(node, edge) } else { let root_label = fragment.vertex_label(0)?.unwrap(); let leaf_label = fragment.vertex_label(fragment.nodes_len() - 1)?.unwrap(); + // dbg!(root_label, leaf_label); PaSe::Segment( self.query_label(root_label).unwrap(), @@ -229,3 +366,122 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Ok(result) } } + +#[cfg(test)] +mod genins_test { + use super::*; + #[allow(unused_imports)] + use crate::{default::DefaultChain, item::default::leaf, Chain}; + + use grammar::test_grammar_helper::*; + + pub fn print_labels( + atom: impl Borrow<DefaultAtom>, + forest: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>, + ) -> Result<(), Box<dyn std::error::Error>> { + let forest = forest.borrow(); + let atom = atom.borrow(); + + for node in forest.nodes() { + let label = forest.vertex_label(node)?; + + if let Some(label) = label { + let label = label.label.label(); + + match label { + GrammarLabelType::TNT(tnt) => { + println!("{tnt} = {}", atom.name_of_tnt(tnt)?); + } + GrammarLabelType::Rule(pos) => { + println!("pos {pos} = {}", atom.rule_pos_string(pos)?); + } + } + } else { + return Err(Error::NodeNoLabel(node).into()); + } + } + + Ok(()) + } + + #[test] + fn test_generate_fragment() -> Result<(), Box<dyn std::error::Error>> { + let grammar = new_notes_grammar()?; + + let atom = DefaultAtom::from_grammar(grammar)?; + + #[cfg(feature = "test-print-viz")] + atom.print_nfa("genins nfa.gv")?; + + let fragment = generate_fragment([72.into(), TNT::Non(0).into()], 0)?; + + let mut test_fragment = leaf!( + GrammarLabel::new(GrammarLabelType::from(72), 0), + GrammarLabel + ); + + test_fragment.plant( + 0, + leaf!( + GrammarLabel::new(GrammarLabelType::from(TNT::Non(0)), 0), + GrammarLabel + ), + false, + )?; + + assert_eq!(fragment, test_fragment); + + // virtual fragments + + println!("nt = 0, t = 3"); + + let virtual_fragment = virtual_generate_fragment(&atom, 0, 3, 0)?; + + assert_eq!(virtual_fragment.nodes_len(), 7); + + let virtual_node = virtual_fragment.vertex_label(5)?.unwrap().label(); + + let test_fragment = generate_fragment( + [ + TNT::Non(0).into(), + 2.into(), + TNT::Non(1).into(), + 8.into(), + TNT::Non(2).into(), + virtual_node.label(), + TNT::Ter(3).into(), + ], + 0, + )?; + + print_labels(&atom, &virtual_fragment)?; + + assert_eq!(virtual_fragment, test_fragment); + + #[cfg(feature = "test-print-viz")] + virtual_fragment.print_viz("virtual fragment (0, 3).gv")?; + + println!("nt = 3, t = 2"); + + let virtual_fragment = virtual_generate_fragment(&atom, 3, 2, 1)?; + + let test_fragment = + generate_fragment([TNT::Non(3).into(), 38.into(), TNT::Ter(2).into()], 1)?; + + print_labels(&atom, &virtual_fragment)?; + + assert_eq!(virtual_fragment, test_fragment); + + #[cfg(feature = "test-print-viz")] + virtual_fragment.print_viz("virtual fragment (3, 2).gv")?; + + // querying reductions + + assert!(matches!(atom.query_reduction(17, 9), Ok(Some(&[1])))); + + assert!(matches!(atom.query_reduction(35, 9), Ok(Some(&[1, 2])))); + assert!(matches!(atom.query_reduction(35, 25), Ok(Some(&[2])))); + + Ok(()) + } +} diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs index 7fafcc8..c614802 100644 --- a/chain/src/item/mod.rs +++ b/chain/src/item/mod.rs @@ -26,7 +26,6 @@ use core::borrow::Borrow; /// /// A segment represents every edge from the root node to the single /// terminating node. -#[allow(unused)] #[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)] pub enum PaSe { /// An edge from a node, as the n-th child. diff --git a/chain/src/plan.org b/chain/src/plan.org index 1da33cc..77d000c 100644 --- a/chain/src/plan.org +++ b/chain/src/plan.org @@ -79,9 +79,9 @@ lack of this step might be the root cause of the failure of the previous version of this project. + [X] Test atoms -- [ ] Implement semiring. [0/5] - + [ ] Define the trait. - + [ ] Define items and rules for the chain-rule parser, as an +- [-] Implement semiring. [2/5] + + [X] Define the trait. + + [X] Define items and rules for the chain-rule parser, as an item-based description. + [ ] Implement the boolean semiring. + [ ] Implement the natural number semiring. |