diff options
Diffstat (limited to 'chain/src')
| -rw-r--r-- | chain/src/item/default/splone.rs | 401 |
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, |