From afad02bdff111ecccb0077b9c989e869723c231c Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 13 Feb 2023 12:28:12 +0800 Subject: Fix phantom edges Previously there was a minor bug: if the chain-rule machine ended in a node without children, which node should be accepting because of edges that have no children and hence were ignored, then since the node has no children, it would be regarded as not accepting. Now this issue is fixed by introducting real or imaginary edges, where an imaginary edge is used to determine the acceptance of nodes without chidlren. --- chain/src/default.rs | 126 +++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 97 insertions(+), 29 deletions(-) (limited to 'chain/src/default.rs') diff --git a/chain/src/default.rs b/chain/src/default.rs index 31c1002..c873de7 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -110,13 +110,13 @@ impl Default for DerIterIndex { } /// A complex type used for storing values of edges with two layers. -type SecondTypeValue = (PaSe, bool, Vec<(Edge, usize)>); +type SecondTypeValue = (PaSe, bool, Vec<(Roi, usize)>); /// An iterator of TwoLayers. #[derive(Debug, Default)] pub struct DerIter { /// Stores edges of only one layer. - singles: Vec<(Edge, usize)>, + singles: Vec<(Roi, usize)>, /// Stores edges with two layers. They are grouped by their /// labels of the second layer. /// @@ -139,7 +139,7 @@ impl DerIter { label: usize, forest_source: PaSe, accepting: bool, - edges: Vec<(Edge, usize)>, + edges: Vec<(Roi, usize)>, ) { if let Some((_, _, vec)) = self.seconds.get_mut(&label) { vec.extend(edges); @@ -449,6 +449,30 @@ impl Chain for DefaultChain { self.current = new; } + fn update_epsilon( + &mut self, + node_id: usize, + edges: impl Iterator, + ) -> Result<(), Self::Error> { + for (roi, _) in edges { + match roi.imaginary_part() { + Some(target) => { + if matches!(self.accepting_vec.get(target).copied(), Some(true)) { + let accepting_vec_len = self.accepting_vec.len(); + + *self + .accepting_vec + .get_mut(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, accepting_vec_len))? = true; + } + } + None => {} + } + } + + Ok(()) + } + type DerIter = DerIter; fn derive(&mut self, t: usize, pos: usize) -> Result { @@ -484,7 +508,7 @@ impl Chain for DefaultChain { child_iter: impl Iterator + ExactSizeIterator + Clone, atom_child_iter: impl Iterator + Clone, pase: PaSe, - mut output: impl AsMut>, + mut output: impl AsMut>, ) -> Result<(), Error> { // First check the values from iterators are all valid. let graph_len = chain.graph.nodes_len(); @@ -516,11 +540,9 @@ impl Chain for DefaultChain { for atom_child in atom_child_iter.clone() { let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap(); - let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap(); + // let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap(); - if !atom_child_empty_node { - num += child_iter.len(); - } + num += child_iter.len(); if atom_child_accepting { num += child_iter_total_degree; @@ -539,16 +561,19 @@ impl Chain for DefaultChain { let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap(); let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap(); - let edge = Edge::new(atom_child, pase, atom_child_accepting); + let roi = Edge::new(atom_child, pase, atom_child_accepting).into(); - if !atom_child_empty_node { - output.extend(child_iter.clone().map(|child| (edge, child))); - } + if atom_child_empty_node { + output.extend(child_iter.clone().map(|child| (child.into(), child))); + } else { + output.extend(child_iter.clone().map(|child| (roi, child))); + }; if atom_child_accepting { for child in child_iter.clone() { for (child_label, child_child) in chain.graph.labels_of(child).unwrap() { - output.extend(child_child.map(|target| (*child_label, target))); + output + .extend(child_child.map(|target| ((*child_label).into(), target))); } } } @@ -666,7 +691,8 @@ impl Chain for DefaultChain { if self.atom.is_empty_node(atom_child).unwrap() { der_iter.singles.extend(child_iter.clone().map(|child| { ( - Edge::new(virtual_node, virtual_pase, accepting), + Edge::new(virtual_node, virtual_pase, accepting) + .into(), child, ) })); @@ -684,7 +710,7 @@ impl Chain for DefaultChain { self.graph.labels_of(child).unwrap().flat_map( |(child_label, child_child_iter)| { child_child_iter.map(|child_child| { - (*child_label, child_child) + ((*child_label).into(), child_child) }) }, ) @@ -716,18 +742,39 @@ mod test_der_iter { let parent = Default::default(); - der_iter.singles.push((Edge::new(0, parent, true), 0)); + der_iter + .singles + .push((Edge::new(0, parent, true).into(), 0)); - der_iter.singles.push((Edge::new(1, parent, true), 0)); + der_iter + .singles + .push((Edge::new(1, parent, true).into(), 0)); - der_iter.singles.push((Edge::new(2, parent, true), 0)); + der_iter + .singles + .push((Edge::new(2, parent, true).into(), 0)); - der_iter.add_second_layer(3, parent, true, vec![(Edge::new(4, parent, true), 1)]); + der_iter.add_second_layer( + 3, + parent, + true, + vec![(Edge::new(4, parent, true).into(), 1)], + ); - der_iter.add_second_layer(6, parent, true, vec![(Edge::new(5, parent, true), 1)]); + der_iter.add_second_layer( + 6, + parent, + true, + vec![(Edge::new(5, parent, true).into(), 1)], + ); // add an entry with a repeated label - der_iter.add_second_layer(3, parent, true, vec![(Edge::new(7, parent, true), 2)]); + der_iter.add_second_layer( + 3, + parent, + true, + vec![(Edge::new(7, parent, true).into(), 2)], + ); assert_eq!( der_iter.next(), @@ -736,8 +783,8 @@ mod test_der_iter { parent, true, vec![ - (Edge::new(4, parent, true), 1), - (Edge::new(7, parent, true), 2) + (Edge::new(4, parent, true).into(), 1), + (Edge::new(7, parent, true).into(), 2) ] )) ); @@ -748,23 +795,23 @@ mod test_der_iter { 6, parent, true, - vec![(Edge::new(5, parent, true), 1)] + vec![(Edge::new(5, parent, true).into(), 1)] )) ); assert_eq!( der_iter.next(), - Some(TwoLayers::One(Edge::new(0, parent, true), 0)) + Some(TwoLayers::One(Edge::new(0, parent, true).into(), 0)) ); assert_eq!( der_iter.next(), - Some(TwoLayers::One(Edge::new(1, parent, true), 0)) + Some(TwoLayers::One(Edge::new(1, parent, true).into(), 0)) ); assert_eq!( der_iter.next(), - Some(TwoLayers::One(Edge::new(2, parent, true), 0)) + Some(TwoLayers::One(Edge::new(2, parent, true).into(), 0)) ); assert_eq!(der_iter.next(), None); @@ -800,6 +847,24 @@ mod test_chain { chain.chain(0, 11)?; chain.chain(0, 12)?; + let forest = &mut chain.forest; + + let node = forest + .query_label(ForestLabel::from(GrammarLabel::new(TNT::Non(6), 6))) + .unwrap(); + + forest.splone(node, Some(13), forest.degree(node)?)?; + + let node = forest + .query_label(ForestLabel::from(GrammarLabel::new(TNT::Non(1), 0))) + .unwrap(); + + forest.splone(node, Some(13), forest.degree(node)?)?; + + forest.splone(0, Some(13), forest.degree(0)?)?; + + forest.print_viz("forest.gv")?; + assert!(matches!(chain.epsilon(), Ok(true))); #[cfg(feature = "test-print-viz")] @@ -823,10 +888,13 @@ mod test_chain { chain.chain(0, 0)?; chain.chain(2, 1)?; chain.chain(2, 2)?; - // chain.chain(2, 3)?; - chain.chain(1, 3)?; + chain.chain(2, 3)?; + chain.chain(1, 4)?; + + chain.forest.print_viz("forest.gv")?; dbg!(chain.current(), chain.history()); + item::default::print_labels(&chain.atom, &chain.forest)?; #[cfg(feature = "test-print-viz")] { -- cgit v1.2.3-18-g5258