From 987c84f3454c687cca0efe0d471fcf00e052ecab Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sun, 12 Feb 2023 12:07:34 +0800 Subject: Added the functionality of split or clone. I need more than the ability to clone nodes: I also need to split the nodes. Now this seems to be correctly added. --- chain/src/item/default/splone.rs | 760 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 760 insertions(+) create mode 100644 chain/src/item/default/splone.rs (limited to 'chain/src/item/default/splone.rs') diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs new file mode 100644 index 0000000..1168539 --- /dev/null +++ b/chain/src/item/default/splone.rs @@ -0,0 +1,760 @@ +//! This module implements a function for "closing" and "splitting" a +//! node in a forest, and hence the name. + +use super::*; +use grammar::TNT; + +fn get_nt_label(label: GrammarLabel) -> Option { + match label.label() { + GrammarLabelType::TNT(TNT::Non(nt)) => Some(nt), + _ => None, + } +} + +fn get_rule_label(label: GrammarLabel) -> Option { + match label.label() { + GrammarLabelType::Rule(rule) => Some(rule), + _ => None, + } +} + +impl DefaultForest> { + /// Either "open split" or "closed split". + /// + /// An open split is an attempt to set the end of the node to + /// `None`, and a closed split is an attempt to set the end to a + /// specific position. + /// + /// Also this function preserves `edge_index + 1` many children + /// when splitting or cloning. + /// + /// To be more precise, this function performs the following + /// actions: + /// + /// 1. Make sure it is labelled by a nonterminal. + /// + /// 2. Check the status of the node. If it is packed, return an + /// error. + /// + /// 3. Make a new label according to the given `end`. See the + /// function + /// [`create_new_label`][DefaultForest::>::create_new_label] + /// for the process of making new labels. + /// + /// 4. If the new label is equal to the old label, and if + /// `edge_index + 1` is equal to the degree of the node, then do + /// nothing. + /// + /// 5. If the new label is equal to the old label but + /// `edge_index+1` is not equal to the degree of the node, then + /// clone the node while preserving `edge_index + 1` many + /// children. + /// + /// 6. If the new label is not equal to the old label, then split + /// the node. See the function + /// [`split_node`][DefaultForest::>::split_node] + /// for details. + /// + /// # Name + /// + /// The name is a mixture of *split* and *clone*. + /// + /// # NOTE + /// + /// We want to "do the same thing" to each parent of the node, + /// that should be checked to be labelled by a rule position. + /// + /// That is to say, if we replace the label of the node, we also + /// replace the label of the "rule parent". If we split the node, + /// the rule parents are also splitted in a parallel manner with + /// the splitted node. + /// + /// Also, when we refer to the parents of the node in the + /// descriptions of procedures below, we actually refer to the + /// parents of the rule parents, which should again be checked to + /// be labelled by non-terminals. + fn splone(&mut self, node: usize, end: Option, edge_index: usize) -> Result<(), Error> { + let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; + + assert!(get_nt_label(node_label.label()).is_some()); + + if node_label.is_packed() { + return Err(Error::SplitPack(node)); + } + + let node_end = node_label.label().end(); + let node_degree = self.degree(node)?; + + // We can check the end to know whether the new label is equal + // to the old label. + if node_end == end { + if node_degree == edge_index + 1 { + return Ok(()); + } + + dbg!(); + self.clone_node(node, edge_index + 1, false)?; + + return Ok(()); + } + + let new_label = self.create_new_label(node, end, edge_index)?; + + let new_label = if let Some(label) = new_label { + label + } else { + return Ok(()); + }; + + if node_end.is_some() + || edge_index + 1 != node_degree + || node_label.clone_index().is_some() + || new_label.clone_index().is_some() + { + return self.split_node(new_label, node, edge_index); + } + + // replace the label directly + + // if new_label.clone_index().is_none() { + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + builder.set_label(node, new_label)?; + + let parents: Vec<_> = builder + .parents_of(node)? + .map(|parent| parent.node()) + .collect(); + + for parent in parents { + let mut parent_label = builder + .vertex_label(parent)? + .ok_or(Error::NodeNoLabel(parent))? + .label(); + + assert!(get_rule_label(parent_label).is_some()); + assert_eq!(builder.degree(parent)?, 1); + + if let Some(pos) = end { + parent_label.set_end(pos); + } else { + parent_label.open_end(); + } + + let parent_label = ForestLabel::from(parent_label); + + builder.set_label(parent, parent_label)?; + } + // } else { + // // REVIEW: Call `split_node` in this situation as well? + + // // If we are here, the new label should have a packed + // // parent. + // let packed = self + // .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed)) + // .unwrap(); + + // let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + // builder.set_label(node, new_label)?; + + // let parents: Vec<_> = builder.parents_of(node)?.collect(); + + // for parent in parents.iter() { + // builder.redirect(parent.node(), parent.edge(), packed)?; + // } + + // builder.add_edge(packed, node, new_label)?; + // } + + Ok(()) + } + + /// Procedure to split the node: + /// + /// 1. Create a new node with the new label. + /// + /// 2. Preserve the old children as specified by `edge_index + 1`. + /// + /// 3. 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. + fn split_node( + &mut self, + new_label: ForestLabel, + mut node: usize, + edge_index: usize, + ) -> Result<(), Error> { + 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_packed = if new_label.clone_index().is_some() { + let packed = builder + .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed)) + .unwrap(); + + builder.add_edge(packed, new_node, new_label)?; + + Some(packed) + } else { + None + }; + + let preserve_children: Vec<_> = builder.children_of(node)?.take(edge_index + 1).collect(); + + for child in preserve_children { + builder.add_edge(new_node, child, new_label)?; + } + + let parents: Vec<_> = { + if let Some(label) = self.vertex_label(node)? { + if label.clone_index().is_some() { + let mut parents = self.parents_of(node)?; + assert_eq!(parents.len(), 1); + node = parents.next().unwrap().node(); + } + } + + let parents: Vec<_> = self.parents_of(node)?.collect(); + + let mut result: Vec<(Parent, usize)> = Vec::with_capacity( + parents + .iter() + .map(|parent| { + self.parents_of(parent.node()) + .map(|iter| iter.len()) + .unwrap_or(0) + }) + .sum(), + ); + + for parent in parents { + let mut parent_label = self + .vertex_label(parent.node())? + .ok_or_else(|| Error::NodeNoLabel(parent.node()))? + .label(); + + assert!(get_rule_label(parent_label).is_some()); + assert_eq!(self.degree(parent.node())?, 1); + + if let Some(pos) = end { + parent_label.set_end(pos); + } else { + parent_label.open_end(); + } + + let parent_label = ForestLabel::from(parent_label); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + let new_parent = builder.add_vertex(parent_label); + + if let Some(packed) = new_packed { + new_node = packed; + } + + builder.add_edge(new_parent, new_node, new_label)?; + + result.extend( + self.parents_of(parent.node())? + .map(|parent_parent| (parent_parent, new_parent)), + ); + } + + result + }; + + for (parent, new_child) in parents { + if self.has_same_children_but_one( + 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(()) + } + + /// Procedure for the new label: + /// + /// 1. Copy the old label. + /// + /// 2. Set the end to `pos`. + /// + /// 3. Pack the label. + /// + /// 4. Check if this label already exists. If so, clone the label and + /// return it. + /// + /// 5. Else set the label to be a plain label. + /// + /// 6. Check if this plain label already exists. If so, clone the + /// existing label, and return the clone of the cloned label. + /// + /// 7. Else return the plain label. + fn create_new_label( + &mut self, + node: usize, + end: Option, + edge_index: usize, + ) -> Result>, Error> { + let mut copied_label = self + .vertex_label(node)? + .ok_or(Error::NodeNoLabel(node))? + .label(); + + if let Some(pos) = end { + copied_label.set_end(pos); + } else { + copied_label.open_end(); + } + + let label = ForestLabel::new(copied_label, ForestLabelType::Packed); + + if let Some(packed) = self.query_label(label) { + for child in self.children_of(packed)? { + if self.has_same_children(child, node, self.degree(child)?, edge_index + 1)? { + return Ok(None); + } + } + + let mut packed_children = self.children_of(packed)?; + + let first_child = packed_children.next().unwrap(); + + let clone_index = self.clone_node(first_child, 0, true)?; + + Ok(Some(ForestLabel::new( + copied_label, + ForestLabelType::Cloned(clone_index), + ))) + } else { + let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain); + + if let Some(existing) = self.query_label(plain_label) { + if self.has_same_children(existing, node, self.degree(existing)?, edge_index + 1)? { + return Ok(None); + } + + let clone_index = self.clone_node(existing, 0, true)?; + + Ok(Some(ForestLabel::new( + copied_label, + ForestLabelType::Cloned(clone_index), + ))) + } else { + Ok(Some(plain_label)) + } + } + } + + /// Compare if two nodes have the same children in the same order. + fn has_same_children( + &self, + nodea: usize, + nodeb: usize, + edge_num_a: usize, + edge_num_b: usize, + ) -> Result { + let children_a = self.children_of(nodea)?.take(edge_num_a); + let children_b = self.children_of(nodeb)?.take(edge_num_b); + + if children_a.len() != children_b.len() { + return Ok(false); + } + + for (childa, childb) in children_a.zip(children_b) { + if childa != childb { + return Ok(false); + } + } + + Ok(true) + } + + /// Detect if a node has a branch that has the same children as + /// another node, except at a given index, where it points to + /// another given node. + fn has_same_children_but_one( + &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 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).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).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)] +mod test_splone { + use super::*; + + use grammar::TNT::*; + + fn create_test_forest( + ) -> Result>, Box> { + let mut forest = leaf!(GrammarLabel::new(Non(0), 0), GrammarLabel); + + forest.plant( + 0, + leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel), + false, + )?; + forest.plant( + 1, + leaf!(GrammarLabel::new_closed(Ter(0), 0, 1), GrammarLabel), + false, + )?; + + forest.plant(0, leaf!(GrammarLabel::new(7, 1), GrammarLabel), false)?; + forest.plant(3, leaf!(GrammarLabel::new(Non(0), 1), GrammarLabel), false)?; + + forest.plant(4, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?; + forest.plant(5, leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel), false)?; + + forest.plant( + 6, + leaf!(GrammarLabel::new_closed(11, 1, 2), GrammarLabel), + false, + )?; + forest.plant( + 7, + leaf!(GrammarLabel::new_closed(Ter(2), 1, 2), GrammarLabel), + false, + )?; + + forest.plant( + 6, + leaf!(GrammarLabel::new_closed(13, 2, 3), GrammarLabel), + false, + )?; + forest.plant( + 9, + leaf!(GrammarLabel::new_closed(Ter(2), 2, 3), GrammarLabel), + false, + )?; + + forest.print_viz("test forest.gv")?; + + Ok(forest) + } + + fn splone_6_3_1() -> Result>, Box> + { + let mut forest = create_test_forest()?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + builder.set_label( + 5, + ForestLabel::new(GrammarLabel::new_closed(3, 1, 3), ForestLabelType::Plain), + )?; + + builder.set_label( + 6, + ForestLabel::new( + GrammarLabel::new_closed(Non(1), 1, 3), + ForestLabelType::Plain, + ), + )?; + + Ok(forest) + } + + fn splone_6_2_0() -> Result>, Box> + { + let mut forest = splone_6_3_1()?; + + let cloned = forest.clone_node(4, 0, false)?; + + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(3, 1, 2), GrammarLabel), + false, + )?; + + forest.plant( + cloned + 1, + leaf!(GrammarLabel::new_closed(Non(1), 1, 2), GrammarLabel), + false, + )?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + builder.add_edge(cloned + 2, 7, dummy_label)?; + + Ok(forest) + } + + fn splone_6_n_0() -> Result>, Box> + { + let mut forest = splone_6_2_0()?; + + let cloned = forest.clone_node(4, 0, false)?; + + forest.plant(cloned, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?; + + forest.plant( + cloned + 1, + leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel), + false, + )?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + builder.add_edge(cloned + 2, 7, dummy_label)?; + + Ok(forest) + } + + fn splone_4_3_0() -> Result>, Box> + { + let mut forest = splone_6_n_0()?; + + let cloned = forest.clone_node(0, 0, false)?; + + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(7, 1, 3), GrammarLabel), + false, + )?; + + forest.plant( + cloned + 1, + leaf!(GrammarLabel::new_closed(Non(0), 1, 3), GrammarLabel), + false, + )?; + + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel), + true, + )?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + builder.add_edge(cloned + 2, 5, dummy_label)?; + + Ok(forest) + } + + fn splone_17_3_0_15_3_0( + ) -> Result>, Box> { + let mut forest = splone_4_3_0()?; + + let to_clone = forest + .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(1), 1, 3))) + .unwrap(); + + let cloned = forest.clone_node(to_clone, 0, false)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + let child = builder + .query_label(ForestLabel::from(GrammarLabel::new_closed(11, 1, 2))) + .unwrap(); + + builder.add_edge(cloned, child, dummy_label)?; + + let to_clone = forest + .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(0), 1, 3))) + .unwrap(); + + let cloned = forest.clone_node(to_clone, 0, false)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let child = builder + .query_label(ForestLabel::from(GrammarLabel::new(3, 1))) + .unwrap(); + + builder.add_edge(cloned, child, dummy_label)?; + + Ok(forest) + } + + #[test] + fn test() -> Result<(), Box> { + let mut test_forest = create_test_forest()?; + + test_forest.splone(6, Some(3), 1)?; + + let answer = splone_6_3_1()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 3 1.gv")?; + panic!("splone(6, Some(3), 1) produced wrong forest"); + } + + test_forest.splone(6, Some(3), 1)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 3 1.gv")?; + panic!("repeated splone(6, Some(3), 1) produced wrong forest"); + } + + test_forest.splone(6, Some(2), 0)?; + + let answer = splone_6_2_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 2 0.gv")?; + panic!("splone(6, Some(2), 0) produced wrong forest"); + } + + test_forest.splone(6, Some(2), 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 2 0.gv")?; + panic!("repeated splone(6, Some(2), 0) produced wrong forest"); + } + + test_forest.splone(6, None, 0)?; + + let answer = splone_6_n_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 None 0.gv")?; + panic!("splone(6, None, 0) produced wrong forest"); + } + + test_forest.splone(14, None, 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 None 0.gv")?; + panic!("repeated splone(6, None, 0) produced wrong forest"); + } + + test_forest.splone(4, Some(3), 0)?; + + let answer = splone_4_3_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 4 3 0.gv")?; + panic!("splone(4, Some(3), 0) produced wrong forest"); + } + + test_forest.splone(4, Some(3), 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 4 3 0.gv")?; + panic!("repeated splone(4, Some(3), 0) produced wrong forest"); + } + + test_forest.splone(17, Some(3), 0)?; + test_forest.splone(15, Some(3), 0)?; + + let answer = splone_17_3_0_15_3_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 17 3 0 15 3 0.gv")?; + 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)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 17 3 0 15 3 0.gv")?; + panic!( + "repeated splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest" + ); + } + + Ok(()) + } +} -- cgit v1.2.3-18-g5258