diff options
Diffstat (limited to 'chain/src/item/default')
| -rw-r--r-- | chain/src/item/default/splone.rs | 100 |
1 files changed, 63 insertions, 37 deletions
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs index 4f4835b..851968c 100644 --- a/chain/src/item/default/splone.rs +++ b/chain/src/item/default/splone.rs @@ -19,6 +19,12 @@ fn get_rule_label(label: GrammarLabel) -> Option<usize> { } } +/// Existing or non-existing label. +enum Eon { + Ex(usize), + Nex(ForestLabel<GrammarLabel>), +} + impl DefaultForest<ForestLabel<GrammarLabel>> { /// Either "open split" or "closed split". /// @@ -56,6 +62,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node] /// for details. /// + /// # Return + /// + /// The function returns the new, splitted or cloned node, or the + /// old node, if nothing is performed. + /// /// # Name /// /// The name is a mixture of *split* and *clone*. @@ -74,12 +85,19 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// 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> { + pub(crate) fn splone( + &mut self, + node: usize, + end: Option<usize>, + edge_index: usize, + ) -> Result<usize, 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() { + self.print_viz("dbg forest.gv").unwrap(); + dbg!(self.vertex_label(node)?, end); return Err(Error::SplitPack(node)); } @@ -89,26 +107,26 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // 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(()); + if node_degree <= edge_index + 1 { + return Ok(node); } - dbg!(); - self.clone_node(node, edge_index + 1, false)?; + let cloned = self.clone_node(node, edge_index + 1, false)?; - return Ok(()); + return Ok(cloned); } let new_label = self.create_new_label(node, end, edge_index)?; - let new_label = if let Some(label) = new_label { - label - } else { - return Ok(()); + let new_label = match new_label { + Eon::Nex(label) => label, + Eon::Ex(existing) => { + return Ok(existing); + } }; if node_end.is_some() - || edge_index + 1 != node_degree + || edge_index + 1 < node_degree || node_label.clone_index().is_some() || new_label.clone_index().is_some() { @@ -168,7 +186,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // builder.add_edge(packed, node, new_label)?; // } - Ok(()) + Ok(node) } /// Procedure to split the node: @@ -180,12 +198,16 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// 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. + /// + /// # Return + /// + /// The function returns the new node index. fn split_node( &mut self, new_label: ForestLabel<GrammarLabel>, mut node: usize, edge_index: usize, - ) -> Result<(), Error> { + ) -> Result<usize, Error> { let end = new_label.label().end(); let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); @@ -269,7 +291,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { }; for (parent, new_child) in parents { - if self.has_same_children_but_one( + if self.has_same_children_until( parent.node(), parent.node(), parent.edge(), @@ -284,18 +306,9 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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(()) + Ok(new_node) } /// Procedure for the new label: @@ -320,7 +333,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { node: usize, end: Option<usize>, edge_index: usize, - ) -> Result<Option<ForestLabel<GrammarLabel>>, Error> { + ) -> Result<Eon, Error> { let mut copied_label = self .vertex_label(node)? .ok_or(Error::NodeNoLabel(node))? @@ -337,7 +350,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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); + return Ok(Eon::Ex(child)); } } @@ -347,7 +360,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let clone_index = self.clone_node(first_child, 0, true)?; - Ok(Some(ForestLabel::new( + Ok(Eon::Nex(ForestLabel::new( copied_label, ForestLabelType::Cloned(clone_index), ))) @@ -356,17 +369,17 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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); + return Ok(Eon::Ex(existing)); } let clone_index = self.clone_node(existing, 0, true)?; - Ok(Some(ForestLabel::new( + Ok(Eon::Nex(ForestLabel::new( copied_label, ForestLabelType::Cloned(clone_index), ))) } else { - Ok(Some(plain_label)) + Ok(Eon::Nex(plain_label)) } } } @@ -396,9 +409,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { } /// 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( + /// another node, until 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_until( &self, nodea: usize, nodeb: usize, @@ -408,14 +426,20 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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() { + if children_a.len() < edge_index + 1 { return Ok(false); } - for (index, (childa, childb)) in children_a.zip(children_b).enumerate() { + 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); @@ -437,11 +461,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let children_a = self.children_of(branch)?; let children_b = children_b.clone(); - if children_a.len() != children_b.len() { + if children_a.len() < edge_index + 1 { continue 'branch_loop; } - for (index, (childa, childb)) in children_a.zip(children_b).enumerate() { + 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; |