summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--chain/src/item/default/splone.rs401
1 files changed, 283 insertions, 118 deletions
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index c73bd9f..2ac3d73 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -137,7 +137,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
|| node_label.clone_index().is_some()
|| new_label.clone_index().is_some()
{
- return self.split_node(new_label, node, edge_index, completingp);
+ return self.split_node(new_label, node_label, node, edge_index, completingp);
}
self.replace_label(node, new_label)?;
@@ -231,7 +231,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
}
};
- let splitted = self.split_node(new_label, node, edge_index, false)?;
+ let splitted = self.split_node(new_label, node_label, node, edge_index, false)?;
self.plant(splitted, fragment, planted)?;
@@ -270,11 +270,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
assert_eq!(builder.degree(parent)?, 1);
- if let Some(pos) = end {
- parent_label.set_end(pos);
- } else {
- parent_label.open_end();
- }
+ parent_label.set_end_option(end);
let parent_label = ForestLabel::from(parent_label);
@@ -301,6 +297,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
fn split_node(
&mut self,
new_label: ForestLabel<GrammarLabel>,
+ old_label: ForestLabel<GrammarLabel>,
mut node: usize,
edge_index: usize,
completingp: bool,
@@ -348,115 +345,28 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
return Ok(new_node);
}
- 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());
-
- 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);
- } 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 {
- builder.add_edge(new_parent, packed, new_label)?;
- } else {
- 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 !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)?;
-
- let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
-
- 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();
+ // We actually have to consider two cases here: one when the
+ // new end is closed, and the other when the new end is open
+ // and the new node is a plain node.
+ //
+ // The former case can be dealt with by cloning the parent,
+ // whereas the latter needs to open the parents recursively
+ // until it meets an open node.
- for child in children_to_add {
- builder.add_edge(cloned, child, new_label)?;
- }
- }
+ if old_label.clone_index().is_some() {
+ let mut parents = self.parents_of(node)?;
+ assert_eq!(parents.len(), 1);
+ node = parents.next().unwrap().node();
}
+ self.split_parents(
+ node,
+ old_label,
+ end,
+ new_packed.unwrap_or(new_node),
+ completingp,
+ )?;
+
Ok(new_node)
}
@@ -500,11 +410,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
.ok_or(Error::NodeNoLabel(node))?
.label();
- if let Some(pos) = end {
- copied_label.set_end(pos);
- } else {
- copied_label.open_end();
- }
+ copied_label.set_end_option(end);
let label = ForestLabel::new(copied_label, ForestLabelType::Packed);
@@ -681,6 +587,265 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
Ok(Some(node))
}
+ /// Split the parents of `node`.
+ ///
+ /// We have created a new node `new_node`, and now we want to
+ /// adjoin it to /proper/ parents so that the labels of parents
+ /// match.
+ ///
+ /// In particular, the rule parents of the old node should have
+ /// the new counter-parts and should be parents of the new node.
+ ///
+ /// Moreover, if the new label is open, we demand that every
+ /// ancestor of the new node be open as well, as a closed node
+ /// cannot contain an open node by definition.
+ fn split_parents(
+ &mut self,
+ node: usize,
+ label: ForestLabel<GrammarLabel>,
+ end: Option<usize>,
+ new_node: usize,
+ completingp: bool,
+ ) -> Result<(), Error> {
+ // First handle the rule parents.
+
+ let parents: Vec<usize> = self.parents_of(node)?.map(|parent| parent.node()).collect();
+
+ let mut ancestors: Vec<(Parent, usize)> = Vec::with_capacity(
+ parents
+ .iter()
+ .copied()
+ .map(|parent| self.parents_of(parent).map_or(0, |iter| iter.len()))
+ .sum(),
+ );
+
+ for parent in parents {
+ let mut parent_label = self
+ .vertex_label(parent)?
+ .ok_or_else(|| Error::NodeNoLabel(parent))?
+ .label();
+
+ #[cfg(debug_assertions)]
+ {
+ assert!(
+ matches!(parent_label.label(), GrammarLabelType::Rule(_)),
+ "this should be a rule parent"
+ );
+
+ if self.degree(parent)? != 1 {
+ dbg!(parent);
+ let _ = self.print_viz("dbg forest.gv");
+
+ panic!("a rule node should not have more than one child");
+ }
+ }
+
+ parent_label.set_end_option(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);
+
+ builder.add_edge(new_parent, new_node, label)?;
+
+ // Open all closed parents if necessary.
+ // dbg!(new_node, label, parent, new_parent, end);
+
+ if end.is_none() {
+ let opened = self.open_ancestors(parent, new_parent)?;
+
+ // dbg!(&opened);
+
+ ancestors.extend(opened);
+ } else {
+ ancestors.extend(
+ self.parents_of(parent)?
+ .map(|parent_parent| (parent_parent, new_parent)),
+ );
+ }
+ }
+
+ // Now clone and add edges, if necessary.
+
+ for (parent, new_child) in ancestors {
+ if !completingp {
+ if self.has_same_children_until(
+ parent.node(),
+ parent.node(),
+ parent.edge(),
+ new_child,
+ )? {
+ continue;
+ }
+
+ // we add no child to parent.edge()-th child here.
+ let cloned = self.clone_node(parent.node(), parent.edge(), false)?;
+
+ dbg!(cloned, parent, new_child);
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ builder.add_edge(cloned, new_child, label)?;
+ } else {
+ if self.has_same_children_except(
+ parent.node(),
+ parent.node(),
+ parent.edge(),
+ new_child,
+ )? {
+ continue;
+ }
+
+ 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, 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, label)?;
+ }
+ }
+ }
+
+ Ok(())
+ }
+
+ /// Open all closed ancestors.
+ fn open_ancestors(
+ &mut self,
+ parent: usize,
+ new_parent: usize,
+ ) -> Result<Vec<(Parent, usize)>, Error> {
+ let mut result = Vec::new();
+
+ let mut stack: Vec<_> = vec![(parent, new_parent)];
+
+ while let Some((top, new_top)) = stack.pop() {
+ // dbg!(top, new_top);
+ let parents: Vec<_> = self.parents_of(top)?.collect();
+
+ 'parent_loop: for parent in parents {
+ // dbg!(parent);
+
+ let parent_node = parent.node();
+ let parent_edge = parent.edge();
+ let parent_label = self
+ .vertex_label(parent_node)?
+ .ok_or(Error::NodeNoLabel(parent_node))?
+ .label();
+
+ if parent_label.end().is_some() {
+ let new_label = self.create_new_label(parent_node, None, parent_edge, None)?;
+
+ let new_label = match new_label {
+ Eon::Nex(label) => label,
+ Eon::Ex(ex_node) => {
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ builder.add_edge(ex_node, new_top, parent_label.into())?;
+
+ continue 'parent_loop;
+ }
+ };
+
+ let new_node_is_clone = new_label.clone_index().is_some();
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ let new_node = builder.add_vertex(new_label);
+
+ let new_packed = if new_node_is_clone {
+ let packed = builder
+ .query_label(ForestLabel::new(
+ new_label.label(),
+ ForestLabelType::Packed,
+ ))
+ .unwrap_or_else(|| {
+ panic!("A cloned node {new_node} without packed nodes")
+ });
+
+ builder.add_edge(packed, new_node, new_label)?;
+
+ Some(packed)
+ } else {
+ builder.add_edge(new_node, new_top, new_label)?;
+ None
+ };
+
+ let preserve_children: Vec<_> = builder
+ .children_of(parent_node)?
+ .take(parent_edge)
+ .collect();
+
+ for child in preserve_children {
+ builder.add_edge(new_node, child, new_label)?;
+ }
+
+ if new_node_is_clone {
+ continue 'parent_loop;
+ }
+
+ // Now deal with new rule parents.
+
+ let rule_parents: Vec<_> = builder
+ .parents_of(parent_node)?
+ .map(|parent| parent.node())
+ .collect();
+
+ for rule_parent in rule_parents {
+ let mut rule_parent_label = self
+ .vertex_label(rule_parent)?
+ .ok_or_else(|| Error::NodeNoLabel(rule_parent))?
+ .label();
+
+ #[cfg(debug_assertions)]
+ {
+ assert!(
+ matches!(rule_parent_label.label(), GrammarLabelType::Rule(_)),
+ "this should be a rule parent"
+ );
+
+ if self.degree(rule_parent)? != 1 {
+ dbg!(rule_parent);
+ let _ = self.print_viz("dbg forest.gv");
+
+ panic!("a rule node should not have more than one child");
+ }
+ }
+
+ rule_parent_label.set_end_option(None);
+
+ let parent_label = ForestLabel::from(rule_parent_label);
+
+ let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
+
+ let new_rule_parent = builder.add_vertex(parent_label);
+
+ builder.add_edge(
+ new_rule_parent,
+ new_packed.unwrap_or(new_node),
+ parent_label,
+ )?;
+
+ stack.push((rule_parent, new_rule_parent));
+ }
+ } else {
+ result.push((parent, new_top));
+ }
+ }
+ }
+
+ Ok(result)
+ }
+
/// Compare if two nodes have the same children in the same order.
fn has_same_children(
&self,