diff options
Diffstat (limited to 'chain/src/item/genins.rs')
| -rw-r--r-- | chain/src/item/genins.rs | 184 |
1 files changed, 63 insertions, 121 deletions
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; } |