summaryrefslogtreecommitdiff
path: root/chain/src/item/default/splone.rs
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src/item/default/splone.rs')
-rw-r--r--chain/src/item/default/splone.rs760
1 files changed, 760 insertions, 0 deletions
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<usize> {
+ match label.label() {
+ GrammarLabelType::TNT(TNT::Non(nt)) => Some(nt),
+ _ => None,
+ }
+}
+
+fn get_rule_label(label: GrammarLabel) -> Option<usize> {
+ match label.label() {
+ GrammarLabelType::Rule(rule) => Some(rule),
+ _ => None,
+ }
+}
+
+impl DefaultForest<ForestLabel<GrammarLabel>> {
+ /// 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::<ForestLabel<GrammarLabel>>::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::<ForestLabel<GrammarLabel>>::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<usize>, 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<GrammarLabel>,
+ 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<usize>,
+ edge_index: usize,
+ ) -> Result<Option<ForestLabel<GrammarLabel>>, 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<bool, Error> {
+ 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<bool, Error> {
+ 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<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> {
+ 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<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+ {
+ 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<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+ {
+ 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<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+ {
+ 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<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
+ {
+ 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<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> {
+ 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<dyn std::error::Error>> {
+ 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(())
+ }
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-09-19 16:37:37 +0000