From b22a5b38161fbc4a0bb9e472d42f78311b73741e Mon Sep 17 00:00:00 2001 From: JSDurand Date: Tue, 28 Feb 2023 15:37:14 +0800 Subject: Add no_item parameter. * chain/src/default.rs: * chain/src/lib.rs: Add a parameter that controls whether or not the chain-rule machine computes the item derivation forest as well. Sometimes we only need to recognize whether an input belongs to the grammar, but do not care about the derivations. This parameter can speed up the machine in that case. --- chain/src/default.rs | 226 +++++++++++++++++++++++++++++++-------------------- 1 file changed, 137 insertions(+), 89 deletions(-) (limited to 'chain/src/default.rs') diff --git a/chain/src/default.rs b/chain/src/default.rs index 08e29ce..7ee460c 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -485,7 +485,12 @@ impl Chain for DefaultChain { // Of course we can use an optional vector to prevent allocating // too much memory for edges whose corresponding vector is empty. - fn derive(&mut self, t: usize, pos: usize) -> Result { + fn derive( + &mut self, + t: usize, + pos: usize, + no_item: bool, + ) -> Result { use TNT::*; /// A helper function to generate edges to join. @@ -610,35 +615,41 @@ impl Chain for DefaultChain { match *atom_label.get_value() { Some(Ter(ter)) if ter == t => { - // prepare forest fragment - - let fragment = - generate_fragment([atom_moved.into(), Ter(ter).into()], pos)?; - - if pos == 4 { - dbg!(atom_moved, label); - self.forest - .print_viz(&format!( - "pos4tb - {atom_moved}-{:?}.gv", - label.true_source() - )) - .unwrap(); - } + let new_pavi: PaVi; - let new_pavi = self.forest.insert_item( - *label, - fragment, - atom_child_iter.clone(), - &self.atom, - )?; + if !no_item { + // prepare forest fragment + + let fragment = + generate_fragment([atom_moved.into(), Ter(ter).into()], pos)?; + + if pos == 4 { + dbg!(atom_moved, label); + self.forest + .print_viz(&format!( + "pos4tb - {atom_moved}-{:?}.gv", + label.true_source() + )) + .unwrap(); + } + + new_pavi = self.forest.insert_item( + *label, + fragment, + atom_child_iter.clone(), + &self.atom, + )?; - if pos == 4 { - self.forest - .print_viz(&format!( - "pos4ta - {atom_moved}-{:?}.gv", - label.true_source() - )) - .unwrap(); + if pos == 4 { + self.forest + .print_viz(&format!( + "pos4ta - {atom_moved}-{:?}.gv", + label.true_source() + )) + .unwrap(); + } + } else { + new_pavi = PaVi::default(); } let accepting = generate_edges( @@ -669,52 +680,60 @@ 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)?; - - if pos == 4 { - dbg!(atom_moved, label); - self.forest - .print_viz(&format!("pos4nb - {atom_moved}-{:?}.gv", label)) - .unwrap(); - } - - let first_segment_pavi = self.forest.insert_item( - *label, - first_fragment, - atom_child_iter.clone(), - &self.atom, - )?; - - if pos == 4 { - self.forest - .print_viz(&format!("pos4na - {atom_moved}-{:?}.gv", label)) - .unwrap(); - } - let accepting = self .atom .is_accepting(virtual_node) .map_err(index_out_of_bounds_conversion)?; - let virtual_fragment = - DefaultForest::new_leaf(GrammarLabel::new(Ter(t), pos)); - - // NOTE: We only need the PaVi from the - // first segment, so we pass an empty - // iterator, in which case the passed - // label is only used for the PaVi. - let virtual_pavi = self.forest.insert_item( - Edge::new(0, first_segment_pavi, accepting), - virtual_fragment, - std::iter::empty(), - &self.atom, - )?; + let first_segment_pavi: PaVi; + let virtual_pavi: PaVi; - if pos == 4 { - self.forest - .print_viz(&format!("pos4va - {atom_moved}-{:?}.gv", label)) - .unwrap(); + if !no_item { + let first_fragment = + generate_fragment([atom_moved.into(), Non(non).into()], pos)?; + + if pos == 4 { + dbg!(atom_moved, label); + self.forest + .print_viz(&format!("pos4nb - {atom_moved}-{:?}.gv", label)) + .unwrap(); + } + + first_segment_pavi = self.forest.insert_item( + *label, + first_fragment, + atom_child_iter.clone(), + &self.atom, + )?; + + if pos == 4 { + self.forest + .print_viz(&format!("pos4na - {atom_moved}-{:?}.gv", label)) + .unwrap(); + } + + let virtual_fragment = + DefaultForest::new_leaf(GrammarLabel::new(Ter(t), pos)); + + // NOTE: We only need the PaVi from the + // first segment, so we pass an empty + // iterator, in which case the passed + // label is only used for the PaVi. + virtual_pavi = self.forest.insert_item( + Edge::new(0, first_segment_pavi, accepting), + virtual_fragment, + std::iter::empty(), + &self.atom, + )?; + + if pos == 4 { + self.forest + .print_viz(&format!("pos4va - {atom_moved}-{:?}.gv", label)) + .unwrap(); + } + } else { + first_segment_pavi = PaVi::default(); + virtual_pavi = PaVi::default(); } let mut new_edges = Vec::new(); @@ -1020,26 +1039,37 @@ mod test_chain { #[test] fn base_test() -> Result<(), Box> { + let mut no_item = false; + + for arg in std::env::args() { + if arg == "no_item" { + no_item = true; + break; + } + } + let grammar = new_notes_grammar()?; let atom = DefaultAtom::from_grammar(grammar)?; let mut chain = DefaultChain::unit(atom)?; - chain.chain(3, 00)?; - chain.chain(1, 01)?; - chain.chain(2, 02)?; - chain.chain(2, 03)?; - chain.chain(2, 04)?; - chain.chain(0, 05)?; - chain.chain(5, 06)?; - chain.chain(1, 07)?; - chain.chain(6, 08)?; - chain.chain(6, 09)?; - chain.chain(6, 10)?; - chain.chain(0, 11)?; - chain.chain(0, 12)?; - - chain.end_of_input()?; + chain.chain(3, 00, no_item)?; + chain.chain(1, 01, no_item)?; + chain.chain(2, 02, no_item)?; + chain.chain(2, 03, no_item)?; + chain.chain(2, 04, no_item)?; + chain.chain(0, 05, no_item)?; + chain.chain(5, 06, no_item)?; + chain.chain(1, 07, no_item)?; + chain.chain(6, 08, no_item)?; + chain.chain(6, 09, no_item)?; + chain.chain(6, 10, no_item)?; + chain.chain(0, 11, no_item)?; + chain.chain(0, 12, no_item)?; + + if !no_item { + chain.end_of_input()?; + } for label in chain.labels_of(chain.current())?.map(|(label, _)| label) { dbg!(label); @@ -1062,20 +1092,29 @@ mod test_chain { #[test] fn test_ambiguity() -> Result<(), Box> { + let mut no_item = false; + + for arg in std::env::args() { + if arg == "no_item" { + no_item = true; + break; + } + } + let grammar = new_paren_grammar()?; let atom = DefaultAtom::from_grammar(grammar)?; let mut chain = DefaultChain::unit(atom)?; - chain.chain(0, 0)?; + chain.chain(0, 0, no_item)?; chain.forest.print_viz("forest0.gv")?; - chain.chain(2, 1)?; + chain.chain(2, 1, no_item)?; chain.forest.print_viz("forest1.gv")?; - chain.chain(2, 2)?; + chain.chain(2, 2, no_item)?; chain.forest.print_viz("forest2.gv")?; - chain.chain(2, 3)?; + chain.chain(2, 3, no_item)?; chain.forest.print_viz("forest3.gv")?; - chain.chain(1, 4)?; + chain.chain(1, 4, no_item)?; chain.forest.print_viz("forest4.gv")?; chain.end_of_input()?; chain.forest.print_viz("forest.gv")?; @@ -1110,6 +1149,15 @@ mod test_chain { #[test] fn test_speed() -> Result<(), Box> { + let mut no_item = false; + + for arg in std::env::args() { + if arg == "no_item" { + no_item = true; + break; + } + } + let grammar = new_notes_grammar_no_regexp()?; println!("grammar: {grammar}"); @@ -1144,7 +1192,7 @@ mod test_chain { let start = std::time::Instant::now(); for (index, t) in input.iter().copied().enumerate() { - chain.chain(t, index)?; + chain.chain(t, index, no_item)?; } let elapsed = start.elapsed(); -- cgit v1.2.3-18-g5258