summaryrefslogtreecommitdiff
path: root/chain/src/item/default
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src/item/default')
-rw-r--r--chain/src/item/default/splone.rs100
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;
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-10 04:04:17 +0000