From 5a5f7e5be9498af219a36401b1d2a13b553402e8 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Tue, 18 Jul 2023 11:55:03 +0800 Subject: Fix a bug of unnecessarily cloning nodes. * chain/src/item/default/splone.rs: Previously when we split nodes, we always clone the parent if the labels differ. This turns out to be incorrect if the new label is open whereas the old label is closed. In that case, the old parent should not contain the new node as a child, as a closed node should not contain an open node. I am not yet entirely sure this fix is correct, so more test await us. --- chain/src/default.rs | 11 ++++++----- chain/src/item/default/extract.rs | 16 +++++++++++++++- chain/src/item/default/mod.rs | 3 +++ chain/src/item/default/splone.rs | 26 +++++++++++++++++++++++--- chain/src/item/genins.rs | 6 ++++++ 5 files changed, 53 insertions(+), 9 deletions(-) (limited to 'chain') diff --git a/chain/src/default.rs b/chain/src/default.rs index 23baa5f..2f6311c 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -802,8 +802,6 @@ impl Chain for DefaultChain { // The 1-th node is a dummy node that should be removed. assert_ne!(root, 1); - // let _ = self.forest.print_viz("help.gv"); - self.forest.remove_node(1)?; let root_degree = self.forest.degree(root)?; @@ -1056,12 +1054,11 @@ mod test_chain { fn test_assumption() -> Result<(), Box> { use grammar::Grammar; - dbg!(); let grammar_str = std::fs::read_to_string( "/Users/durand/Desktop/Centre/A propos de programmes/Rust/rep/grammar/abnf grammars/test.abnf", ) .unwrap(); - dbg!(); + let grammar: Grammar = grammar_str.parse()?; let atom = DefaultAtom::from_grammar(grammar)?; @@ -1071,9 +1068,13 @@ mod test_chain { let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 1, 0, 1]; + let to_print = std::fs::metadata("output/").is_ok(); + for (pos, t) in input.iter().copied().enumerate().take(2) { chain.chain(t, pos, no_item)?; - // chain.forest().print_viz(&format!("forest {pos}.gv"))?; + if to_print { + chain.forest().print_viz(&format!("forest {pos}.gv"))?; + } dbg!(pos, t); } diff --git a/chain/src/item/default/extract.rs b/chain/src/item/default/extract.rs index 96f5119..b99c541 100644 --- a/chain/src/item/default/extract.rs +++ b/chain/src/item/default/extract.rs @@ -188,11 +188,25 @@ impl DefaultForest> { 1 => { let child = *roots_stack.first().unwrap(); - builder.add_vertex(self.vertex_label(child)?.ok_or(Error::NodeNoLabel(child))?); + // Make this a plain node. + // + // This situation will be handled properly in + // later codes. + + let plain_child_label = ForestLabel::new( + self.vertex_label(child)? + .ok_or(Error::NodeNoLabel(child))? + .label(), + ForestLabelType::Plain, + ); + + builder.add_vertex(plain_child_label); } _ => { let builder_root = builder.add_vertex(original_root_label); + // The clone indices have to be preserved so that + // we can track those nodes later. for child in roots_stack.iter().copied() { let child_node = builder.add_vertex( self.vertex_label(child)?.ok_or(Error::NodeNoLabel(child))?, diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs index 0781dd2..7369c6f 100644 --- a/chain/src/item/default/mod.rs +++ b/chain/src/item/default/mod.rs @@ -1,3 +1,4 @@ +#![debugger_visualizer(gdb_script_file = "printer.py")] //! This module provides a default implementation of iten derivation //! forest. @@ -72,6 +73,8 @@ impl From for Error { } } +// FIXME: Provide a better Debug implementation. + /// A default implementation of forest. #[derive(Debug, Clone, Graph)] pub struct DefaultForest { diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs index 09fca0b..c73bd9f 100644 --- a/chain/src/item/default/splone.rs +++ b/chain/src/item/default/splone.rs @@ -290,7 +290,8 @@ impl DefaultForest> { /// /// 2. Preserve the old children as specified by `edge_index + 1`. /// - /// 3. For each parent, clone the parent. Replace the original + /// 3. If the new node is closed or if the new node is not cloned, + /// then for each parent, clone the parent. Replace the original /// child of the parent, which pointed to the old node, by this /// new node. Other children are inherited from the old parent. /// @@ -305,15 +306,16 @@ impl DefaultForest> { completingp: bool, ) -> Result { let end = new_label.label().end(); + let new_node_is_clone = new_label.clone_index().is_some(); let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); let new_node = builder.add_vertex(new_label); - let new_packed = if new_label.clone_index().is_some() { + let new_packed = if new_node_is_clone { let packed = builder .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed)) - .unwrap(); + .unwrap_or_else(|| panic!("A cloned node {new_node} without packed nodes")); builder.add_edge(packed, new_node, new_label)?; @@ -328,6 +330,24 @@ impl DefaultForest> { builder.add_edge(new_node, child, new_label)?; } + // NOTE: If the label of the parent is closed while the node + // label is open ended, we need to use an opened parent + // instead. + // + // To be specific, we only need to split the parent if the new + // label is closed. This can be seen from the fact that this + // function only deals with the situation that the new label + // and the old label are different. In this situation, if the + // new label is closed, it means we are closing a node under + // an open node, and we need to clone that parent indeed. On + // the other hand, if we are opening a node under a closed + // node, that parent does not need to connect to this new + // node. + + if end.is_none() && new_node_is_clone { + return Ok(new_node); + } + let parents: Vec<_> = { if let Some(label) = self.vertex_label(node)? { if label.clone_index().is_some() { diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index ac521cc..07dbdfb 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -720,6 +720,12 @@ impl DefaultForest> { // return Err(Error::CannotClose(nt, t, node, node_label_start)); // } + // FIXME: It is not correct to set the end of all + // nodes unconditionally here. + // + // We need to figure out the correct way to set the + // ending positions. + for frag in reduction_fragment.into_iter().flatten() { let mut frag = frag.clone(); frag.set_pos(node_label_start, true)?; -- cgit v1.2.3-18-g5258