From fbaa420ed550e9c3e7cdc09d4a8ec22bfbd782a6 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 27 Feb 2023 12:36:41 +0800 Subject: before a major refactor I decide to adopt a new approach of recording and updating item derivation forests. Since this affects a lot of things, I decide to commit before the refactor, so that I can create a branch for that refactor. --- chain/src/item/default/splone.rs | 187 ++++++++++++++++++++++++++++++++------- 1 file changed, 156 insertions(+), 31 deletions(-) (limited to 'chain/src/item/default/splone.rs') diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs index 851968c..237b92a 100644 --- a/chain/src/item/default/splone.rs +++ b/chain/src/item/default/splone.rs @@ -1,4 +1,3 @@ -#![allow(dead_code)] //! This module implements a function for "closing" and "splitting" a //! node in a forest, and hence the name. @@ -20,6 +19,7 @@ fn get_rule_label(label: GrammarLabel) -> Option { } /// Existing or non-existing label. +#[derive(Debug, Copy, Clone)] enum Eon { Ex(usize), Nex(ForestLabel), @@ -62,6 +62,12 @@ impl DefaultForest> { /// [`split_node`][DefaultForest::>::split_node] /// for details. /// + /// # `completingp` + /// + /// When we are completing the forest at the end, we do not wish + /// to keep the nodes at the end, so we pass a flag to inform the + /// function of this intention. + /// /// # Return /// /// The function returns the new, splitted or cloned node, or the @@ -90,6 +96,7 @@ impl DefaultForest> { node: usize, end: Option, edge_index: usize, + completingp: bool, ) -> Result { let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; @@ -130,7 +137,7 @@ impl DefaultForest> { || node_label.clone_index().is_some() || new_label.clone_index().is_some() { - return self.split_node(new_label, node, edge_index); + return self.split_node(new_label, node, edge_index, completingp); } // replace the label directly @@ -151,6 +158,11 @@ impl DefaultForest> { .ok_or(Error::NodeNoLabel(parent))? .label(); + if get_rule_label(parent_label).is_none() { + self.print_viz("dbg forest.gv").unwrap(); + panic!("assumption fails"); + } + assert!(get_rule_label(parent_label).is_some()); assert_eq!(builder.degree(parent)?, 1); @@ -207,12 +219,13 @@ impl DefaultForest> { new_label: ForestLabel, mut node: usize, edge_index: usize, + completingp: bool, ) -> Result { let end = new_label.label().end(); let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); - let mut new_node = builder.add_vertex(new_label); + let new_node = builder.add_vertex(new_label); let new_packed = if new_label.clone_index().is_some() { let packed = builder @@ -261,7 +274,13 @@ impl DefaultForest> { .label(); assert!(get_rule_label(parent_label).is_some()); - assert_eq!(self.degree(parent.node())?, 1); + + if self.degree(parent.node())? != 1 { + dbg!(parent); + self.print_viz("dbg forest.gv").unwrap(); + + panic!("assumption fails"); + } if let Some(pos) = end { parent_label.set_end(pos); @@ -276,11 +295,11 @@ impl DefaultForest> { let new_parent = builder.add_vertex(parent_label); if let Some(packed) = new_packed { - new_node = packed; + builder.add_edge(new_parent, packed, new_label)?; + } else { + builder.add_edge(new_parent, new_node, new_label)?; } - builder.add_edge(new_parent, new_node, new_label)?; - result.extend( self.parents_of(parent.node())? .map(|parent_parent| (parent_parent, new_parent)), @@ -291,21 +310,48 @@ impl DefaultForest> { }; for (parent, new_child) in parents { - if self.has_same_children_until( - parent.node(), - parent.node(), - parent.edge(), - new_child, - )? { - continue; - } + if !completingp { + if self.has_same_children_until( + parent.node(), + parent.node(), + parent.edge(), + new_child, + )? { + continue; + } - // we don't add a child to parent.edge() here. - let cloned = self.clone_node(parent.node(), parent.edge(), false)?; + // we don't add a child to parent.edge() here. + let cloned = self.clone_node(parent.node(), parent.edge(), false)?; - let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); - builder.add_edge(cloned, new_child, new_label)?; + builder.add_edge(cloned, new_child, new_label)?; + } else { + if self.has_same_children_except( + parent.node(), + parent.node(), + parent.edge(), + new_child, + )? { + continue; + } + + // we don't add a child to parent.edge() here. + let cloned = self.clone_node(parent.node(), parent.edge(), false)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + builder.add_edge(cloned, new_child, new_label)?; + + let children_to_add: Vec<_> = builder + .children_of(parent.node())? + .skip(parent.edge() + 1) + .collect(); + + for child in children_to_add { + builder.add_edge(cloned, child, new_label)?; + } + } } Ok(new_node) @@ -486,6 +532,85 @@ impl DefaultForest> { unreachable!("should not examine children of a packed node") } } + + /// Detect if a node has a branch that has the same children as + /// another node, except for a given index, where it points to another + /// given node. + /// + /// # Clones + /// + /// If `nodea` is a clone, it checks every clone to see if the + /// condition is satisfied for some clone. + fn has_same_children_except( + &self, + nodea: usize, + nodeb: usize, + edge_index: usize, + alternative: usize, + ) -> Result { + let labela = self.vertex_label(nodea)?.ok_or(Error::NodeNoLabel(nodea))?; + let children_b = self.children_of(nodeb)?; + + if children_b.len() < edge_index + 1 { + return Err(Error::IndexOutOfBounds(edge_index, children_b.len() - 1)); + } + + if labela.is_plain() { + let children_a = self.children_of(nodea)?; + + if children_a.len() != children_b.len() { + return Ok(false); + } + + for (index, (childa, childb)) in + children_a.zip(children_b).take(edge_index + 1).enumerate() + { + if index != edge_index { + if childa != childb { + return Ok(false); + } + } else if childa != alternative { + return Ok(false); + } + } + + Ok(true) + } else if labela.clone_index().is_some() { + let mut parentsa = self.parents_of(nodea)?; + + assert_eq!(parentsa.len(), 1); + + let parenta = parentsa.next().unwrap().node(); + + 'branch_loop: for branch in self.children_of(parenta)? { + let children_a = self.children_of(branch)?; + let children_b = children_b.clone(); + + if children_a.len() < children_b.len() { + continue 'branch_loop; + } + + for (index, (childa, childb)) in + children_a.zip(children_b).take(edge_index + 1).enumerate() + { + if index != edge_index { + if childa != childb { + continue 'branch_loop; + } + } else if childa != alternative { + continue 'branch_loop; + } + } + + return Ok(true); + } + + Ok(false) + } else { + // a packed node; this should not happen + unreachable!("should not examine children of a packed node") + } + } } #[cfg(test)] @@ -688,7 +813,7 @@ mod test_splone { fn test() -> Result<(), Box> { let mut test_forest = create_test_forest()?; - test_forest.splone(6, Some(3), 1)?; + test_forest.splone(6, Some(3), 1, false)?; let answer = splone_6_3_1()?; @@ -698,7 +823,7 @@ mod test_splone { panic!("splone(6, Some(3), 1) produced wrong forest"); } - test_forest.splone(6, Some(3), 1)?; + test_forest.splone(6, Some(3), 1, false)?; if test_forest != answer { test_forest.print_viz("sploned forest.gv")?; @@ -706,7 +831,7 @@ mod test_splone { panic!("repeated splone(6, Some(3), 1) produced wrong forest"); } - test_forest.splone(6, Some(2), 0)?; + test_forest.splone(6, Some(2), 0, false)?; let answer = splone_6_2_0()?; @@ -716,7 +841,7 @@ mod test_splone { panic!("splone(6, Some(2), 0) produced wrong forest"); } - test_forest.splone(6, Some(2), 0)?; + test_forest.splone(6, Some(2), 0, false)?; if test_forest != answer { test_forest.print_viz("sploned forest.gv")?; @@ -724,7 +849,7 @@ mod test_splone { panic!("repeated splone(6, Some(2), 0) produced wrong forest"); } - test_forest.splone(6, None, 0)?; + test_forest.splone(6, None, 0, false)?; let answer = splone_6_n_0()?; @@ -734,7 +859,7 @@ mod test_splone { panic!("splone(6, None, 0) produced wrong forest"); } - test_forest.splone(14, None, 0)?; + test_forest.splone(14, None, 0, false)?; if test_forest != answer { test_forest.print_viz("sploned forest.gv")?; @@ -742,7 +867,7 @@ mod test_splone { panic!("repeated splone(6, None, 0) produced wrong forest"); } - test_forest.splone(4, Some(3), 0)?; + test_forest.splone(4, Some(3), 0, false)?; let answer = splone_4_3_0()?; @@ -752,7 +877,7 @@ mod test_splone { panic!("splone(4, Some(3), 0) produced wrong forest"); } - test_forest.splone(4, Some(3), 0)?; + test_forest.splone(4, Some(3), 0, false)?; if test_forest != answer { test_forest.print_viz("sploned forest.gv")?; @@ -760,8 +885,8 @@ mod test_splone { panic!("repeated splone(4, Some(3), 0) produced wrong forest"); } - test_forest.splone(17, Some(3), 0)?; - test_forest.splone(15, Some(3), 0)?; + test_forest.splone(17, Some(3), 0, false)?; + test_forest.splone(15, Some(3), 0, false)?; let answer = splone_17_3_0_15_3_0()?; @@ -771,8 +896,8 @@ mod test_splone { panic!("splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest"); } - test_forest.splone(17, Some(3), 0)?; - test_forest.splone(15, Some(3), 0)?; + test_forest.splone(17, Some(3), 0, false)?; + test_forest.splone(15, Some(3), 0, false)?; if test_forest != answer { test_forest.print_viz("sploned forest.gv")?; -- cgit v1.2.3-18-g5258