diff options
Diffstat (limited to 'chain/src/item')
| -rw-r--r-- | chain/src/item/default/splone.rs | 100 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 184 |
2 files changed, 126 insertions, 158 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; diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 43807f8..4c51d9a 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -25,6 +25,12 @@ fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { _ => Error::Invalid, } } + +/// Determine if a label is labelled by a terminal. +fn is_labelled_by_terminal(label: GrammarLabelType) -> bool { + matches!(label.tnt(), Some(t) if matches!(t, TNT::Ter(_))) +} + /// A helper function to generate a fragment of forest. /// /// It simply constructs a root node and then appends @@ -38,30 +44,43 @@ pub fn generate_fragment( labels: impl AsRef<[GrammarLabelType]>, pos: usize, ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, crate::default::Error> { - let mut labels_iter = labels.as_ref().iter(); - let mut result: DefaultForest<ForestLabel<GrammarLabel>>; - - if let Some(first_label) = labels_iter.next() { - result = DefaultForest::new_leaf(GrammarLabel::new(*first_label, pos)); - - let mut index = 0; - - for label in labels_iter { - result.plant( - index, - DefaultForest::new_leaf(GrammarLabel::new(*label, pos)), - false, - )?; - - // To prevent duplication of labels causing - // panics, we query the index of the new node. - index = result - .query_label(GrammarLabel::new(*label, pos).into()) - // REVIEW: Perhaps a LabelNoNode error? - .ok_or(Error::Invalid)?; - } + let labels_slice = labels.as_ref(); + + let labels_len = labels_slice.len(); + + let last_label = if labels_len > 0 { + labels_slice.get(labels_len - 1).copied().unwrap() } else { - result = Default::default(); + return Ok(Default::default()); + }; + + let labels_iter = labels_slice.iter(); + + let labels_iter_zipped = labels_iter + .clone() + .zip(labels_iter.skip(1).chain(std::iter::once(&last_label))); + + let mut mapped_iter = labels_iter_zipped.map(|(label, next_label)| { + if is_labelled_by_terminal(*next_label) { + GrammarLabel::new_closed(*label, pos, pos + 1) + } else { + GrammarLabel::new(*label, pos) + } + }); + + let first_label = mapped_iter.next().unwrap(); + + let mut result = DefaultForest::new_leaf(first_label); + + let mut index = 0; + + for label in mapped_iter { + result.plant(index, DefaultForest::new_leaf(label), false)?; + + index = result + .query_label(label.into()) + // REVIEW: Perhaps a LabelNoNode error? + .ok_or(Error::Invalid)?; } Ok(result) @@ -123,7 +142,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { &mut self, label: Edge, fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>, - atom_child_iter: impl Iterator<Item = usize>, + atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator, atom: &DefaultAtom, ) -> Result<PaSe, Error> { let fragment = fragment.borrow(); @@ -243,8 +262,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // locate the nodes for reduction_nt in reduction_info.iter().copied().flatten().rev() { while let Some(mut node) = stack.pop() { - // REVIEW: A lot of labels appear here. - // Perhaps I need to refactor something? let mut node_label = self .vertex_label(node.node())? .ok_or_else(|| Error::NodeNoLabel(node.node()))?; @@ -255,53 +272,32 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { .label(), GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt ) { - // TODO: Try to update the end index of the - // node; if the node already has an ending - // index, clone the node, and update the - // ending index of the cloned node; otherwise, - // just set the ending index. - - if node_label.label().end().is_some() { - let cloned_node = - self.clone_node(node.node(), node.edge() + 1, false)?; - - self.transform_label(cloned_node, |mut label| { - label.set_end(pos + 1); - label - })?; - - node_label = self - .vertex_label(node.node())? - .ok_or_else(|| Error::NodeNoLabel(node.node()))?; - } else { - self.transform_label(node.node(), |mut label| { - label.set_end(pos + 1); - label - })?; - } + let sploned_node = self.splone(node.node(), Some(pos), node.edge())?; + + node_label = self + .vertex_label(sploned_node)? + .ok_or(Error::NodeNoLabel(sploned_node))?; if node_label.clone_index().is_some() { - let mut parent_iter = self.parents_of(node.node())?; + let mut parent_iter = self.parents_of(sploned_node)?; #[cfg(debug_assertions)] - assert_eq!(parent_iter.len(), 1); + { + assert_eq!(parent_iter.len(), 1); - node = parent_iter.next().unwrap(); + assert!(self + .vertex_label(sploned_node)? + .ok_or(Error::NodeNoLabel(sploned_node))? + .is_packed()); + } - #[cfg(debug_assertions)] - assert!(self - .vertex_label(node.node())? - .ok_or_else(|| Error::NodeNoLabel(node.node()))? - .is_packed()); + node = parent_iter.next().unwrap(); + } else { + node = Parent::new(sploned_node, node.edge()); } let parents_iter = self.parents_of(node.node())?; - let to_update = parents_iter - .clone() - .map(|parent| parent.node()) - .collect::<Vec<_>>(); - for parent in parents_iter { let parent_label = self .vertex_label(parent.node())? @@ -312,14 +308,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { crate::item::default::print_labels(atom, self.borrow()).unwrap(); self.print_viz("dbg forest.gv").unwrap(); - dbg!(parent, parent_label, label, node); + dbg!(parent, parent_label, label, node, sploned_node); panic!("assumption fails"); } - // debug_assert!(parent_label.label().rule().is_some()); - // debug_assert!(parent_label.end().is_none()); - second_stack.extend(self.parents_of(parent.node())?.filter(|n| { matches!(self.vertex_label(n.node()), Ok(Some(label)) @@ -328,13 +321,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Some(TNT::Non(_)))) })); } - - for node in to_update { - self.transform_label(node, |mut label| { - label.set_end(pos + 1); - label - })?; - } } } @@ -357,59 +343,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { self.print_viz("dbg forest.gv").unwrap(); #[cfg(test)] - genins_test::print_labels(atom, self).unwrap(); + genins_test::print_labels(atom, self.borrow()).unwrap(); return Err(Error::CannotPlant); } for parent in stack.into_iter() { - let was_last_child = parent.edge() + 1 >= self.degree(parent.node())?; - - let overlap = { - if let Ok(child) = self.nth_child(parent.node(), parent.edge()) { - let edge_th_child = child; - let child_label = self - .vertex_label(edge_th_child)? - .ok_or(Error::NodeNoLabel(edge_th_child))?; - let child_start = child_label.label().start(); - let child_end = child_label.label().end(); - - child_start >= pos || matches!(child_end, Some(end) if end > pos) - } else { - // the root case - false - } - }; + let sploned_node = self.splone(parent.node(), None, parent.edge())?; - if overlap { - let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?; - - self.plant(cloned_node, fragment, non_empty)?; - } else if was_last_child { - // dbg!(&fragment); - self.plant(parent.node(), fragment, non_empty)?; - } else { - let nth_child = self.nth_child(parent.node(), parent.edge() + 1)?; - - if self.is_prefix(nth_child, fragment)? { - // do nothing - continue; - } - - // dbg!( - // label, - // atom_child, - // &parents, - // reduction_info, - // atom.query_reduction(label.label(), atom_child).unwrap() - // ); - - // self.print_viz("dbg forest.gv").unwrap(); - - let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?; - - self.plant(cloned_node, fragment, non_empty)?; - } + self.plant(sploned_node, fragment, non_empty)?; non_empty = true; } |