From 081e3d2ed8d3f9b4e4d6fd864283a4230e09b25a Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 21 Jul 2023 11:43:53 +0800 Subject: chain/default: Remove the annoying node whenever plausible. The chain-rule machine needs a place-holder node at the beginning. But afterwards that node is pure annoyance and disturbs the functioning of the machine. Consequently I removed that node whenever the right time comes. This seems to fix some other bugs. It is reasonable: the presence of that bogus node is just noise to the machine and error-prone. --- chain/src/default.rs | 128 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 119 insertions(+), 9 deletions(-) diff --git a/chain/src/default.rs b/chain/src/default.rs index 2f6311c..97dbfa3 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -365,7 +365,7 @@ impl Chain for DefaultChain { let initial_nullable = atom .is_nullable(START_NONTERMINAL) - .map_err(|_| Error::IndexOutOfBounds(0, atom.non_num()))?; + .map_err(|_| Error::IndexOutOfBounds(START_NONTERMINAL, atom.non_num()))?; builder.add_edge( first, @@ -569,6 +569,21 @@ impl Chain for DefaultChain { Ok(accepting) } + if !no_item + && self.forest.nodes_len() > 2 + && matches!(self.forest.degree(1), Ok(d) if d > 0) + { + // dbg!(self.forest.vertex_label(1)?, self.atom.empty()); + match self.forest.vertex_label(1) { + Ok(Some(label)) => { + if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) { + self.forest.remove_node(1)?; + } + } + _ => {} + } + } + let mut der_iter = DerIter::default(); let mut accepting_pavi: HashSet = HashSet::new(); @@ -813,9 +828,91 @@ impl Chain for DefaultChain { dbg!(root_degree, root_label); + // First perform reduction. + + let _ = self.forest.print_viz("forest before reduction.gv"); + + // self.forest.reduction(root, pos, ter, &self.atom, true)?; + // REVIEW: Why nodes? let mut nodes = Vec::with_capacity(root_degree); + // let nodes_len = self.forest.nodes_len(); + + // let mut stack: Vec<(usize, ForestLabel)> = Vec::with_capacity(nodes_len); + // let mut visited: Vec<_> = std::iter::repeat(false).take(nodes_len).collect(); + + // macro_rules! visited { + // ($node: expr) => { + // visited.get($node).copied() == Some(true) + // }; + // } + + // macro_rules! visit { + // ($node: expr) => { + // *visited + // .get_mut($node) + // .ok_or(Error::IndexOutOfBounds($node, nodes_len))? = true; + // }; + // } + + // stack.push((root, root_label)); + + // while let Some((top, top_label)) = stack.pop() { + // if top_label.is_packed() { + // visit!(top); + + // for clone in self.forest.children_of(top)? { + // let cloned_label = self + // .forest + // .vertex_label(clone)? + // .ok_or(Error::NodeNoLabel(clone))?; + // stack.push((clone, cloned_label)); + // } + // } else if top_label.clone_index().is_some() { + // let visited = visited!(top); + + // if visited { + // // every child should have been processed + + // if top_label.label().end().is_some() { + // continue; + // } + + // for child in self.forest.children_of(top)? { + // let child_label = self + // .forest + // .vertex_label(child)? + // .ok_or(Error::NodeNoLabel(child))?; + + // if child_label.label().end().is_none() { + // continue; + // } + // } + + // } else { + // visit!(top); + + // stack.push((top, top_label)); + + // for child in self.forest.children_of(top)? { + // if visited!(child) { + // continue; + // } + + // let child_label = self + // .forest + // .vertex_label(child)? + // .ok_or(Error::NodeNoLabel(child))?; + + // stack.push((child, child_label)); + // } + // } + // } else { + // // + // } + // } + if root_label.is_packed() { let mut all_completed_clones = Vec::with_capacity(root_degree); @@ -884,11 +981,15 @@ impl Chain for DefaultChain { nodes.push(self.forest.reduction(root, pos, ter, &self.atom, true)?); } - dbg!(&nodes); + // dbg!(&nodes); - // self.forest - // .print_viz("forest before extraction.gv") - // .unwrap(); + println!("printing grammar"); + println!("{}", &(*self.atom)); + self.atom.print_nullables(); + self.atom.print_virtual(); + let _ = item::default::print_labels(&self.atom, &self.forest); + + let _ = self.forest.print_viz("forest before extraction.gv"); result = self.forest.extract(pos)?; @@ -1066,11 +1167,14 @@ mod test_chain { let no_item = false; - let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 1, 0, 1]; + let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 0, 1, 4, 2, 2, 1]; + + let input_len = input.len(); - let to_print = std::fs::metadata("output/").is_ok(); + // let to_print = std::fs::metadata("output/").is_ok(); + let to_print = false; - for (pos, t) in input.iter().copied().enumerate().take(2) { + for (pos, t) in input.iter().copied().enumerate().take(input_len) { chain.chain(t, pos, no_item)?; if to_print { chain.forest().print_viz(&format!("forest {pos}.gv"))?; @@ -1078,7 +1182,13 @@ mod test_chain { dbg!(pos, t); } - item::default::print_labels(&chain.atom, &chain.forest)?; + // let _ = chain.forest.print_viz("forest before extraction.gv"); + + let extracted = chain.end_of_input(input_len, input[input_len - 1])?; + + let _ = extracted.print_viz("extracted forest.gv"); + + // item::default::print_labels(&chain.atom, &chain.forest)?; Ok(()) } -- cgit v1.2.3-18-g5258