Fix phantom edges

Previously there was a minor bug: if the chain-rule machine ended in a
node without children, which node should be accepting because of edges
that have no children and hence were ignored, then since the node has
no children, it would be regarded as not accepting.  Now this issue is
fixed by introducting real or imaginary edges, where an imaginary edge
is used to determine the acceptance of nodes without chidlren.

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;
             }