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, 84 insertions, 14 deletions

diff --git a/chain/src/lib.rs b/chain/src/lib.rs
index 745ad5a..a7740c2 100644
--- a/chain/src/lib.rs
+++ b/chain/src/lib.rs
@@ -64,12 +64,59 @@ impl core::fmt::Display for Edge {
     }
 }
 
-// TODO: Define an enumeration that stands for either an edge or a
-// "phantom" edge.
-//
-// A phantom edge will be ignored when adding edges.  The phantom
-// edges will be used to determine the acceptance of a node, when and
-// only when that new node turns out to have no children.
+/// A Real Or Imaginary edge.
+///
+/// An imaginary edge will be ignored when adding edges.  The
+/// imaginary edges will be used to determine the acceptance of a
+/// node, when and only when that new node turns out to have no
+/// children.
+///
+/// # Note
+///
+/// Non, je ne suis pas un roi.  Je ne sais pas qu'est-ce que vous
+/// parlez.
+#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub enum Roi {
+    /// A real edge is an ordinary edge.
+    Re(Edge),
+    /// The label of an imaginary edge is not important, so we only
+    /// record its target.
+    Im(usize),
+}
+
+// Some convenient conversions
+
+impl From<Edge> for Roi {
+    fn from(edge: Edge) -> Self {
+        Self::Re(edge)
+    }
+}
+
+impl From<usize> for Roi {
+    fn from(target: usize) -> Self {
+        Self::Im(target)
+    }
+}
+
+impl Roi {
+    /// Return the real part if it is a real edge.
+    fn real_part(self) -> Option<Edge> {
+        if let Self::Re(edge) = self {
+            Some(edge)
+        } else {
+            None
+        }
+    }
+
+    /// Return the imaginary part if it is an imaginary edge.
+    fn imaginary_part(self) -> Option<usize> {
+        if let Self::Im(target) = self {
+            Some(target)
+        } else {
+            None
+        }
+    }
+}
 
 /// Each derivation is a concatenation of two items, so there are two
 /// layers.  But some items have no children and are accepting, in
@@ -81,7 +128,7 @@ impl core::fmt::Display for Edge {
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum TwoLayers {
     /// One layer has no children.
-    One(Edge, usize),
+    One(Roi, usize),
     // REVIEW: Maybe we do not need to store an edge in the forest: we
     // only need the source of the edge?
     /// Both layers have children.
@@ -90,7 +137,7 @@ pub enum TwoLayers {
     /// the source of the associated forest edge of the second layer,
     /// and the third is a list of edges, which are the common first
     /// layers.
-    Two(usize, PaSe, bool, Vec<(Edge, usize)>),
+    Two(usize, PaSe, bool, Vec<(Roi, usize)>),
 }
 
 /// The type of a collapsed iterator.
@@ -122,7 +169,7 @@ where
     I: Iterator<Item = TwoLayers>,
     C: Chain<DerIter = I>,
 {
-    type Item = Result<(Edge, usize), <C as Chain>::Error>;
+    type Item = Result<(Roi, usize), <C as Chain>::Error>;
 
     fn next(&mut self) -> Option<Self::Item> {
         if self.stop {
@@ -133,7 +180,11 @@ where
             match two_layer {
                 TwoLayers::One(edge, to) => Some(Ok((edge, to))),
                 TwoLayers::Two(label, forest_source, accepting, edges) => {
-                    let new_index = match self.chain.extend(edges.into_iter()) {
+                    let new_index = match self.chain.extend(
+                        edges
+                            .into_iter()
+                            .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, target))),
+                    ) {
                         Ok(new) => new,
                         Err(error) => {
                             // Prevent further iterations.
@@ -143,7 +194,10 @@ where
                         }
                     };
 
-                    Some(Ok((Edge::new(label, forest_source, accepting), new_index)))
+                    Some(Ok((
+                        Edge::new(label, forest_source, accepting).into(),
+                        new_index,
+                    )))
                 }
             }
         } else {
@@ -174,6 +228,14 @@ pub trait Chain: LabelExtGraph<Edge> {
     /// Update the history
     fn update_history(&mut self, new: usize);
 
+    /// Update the acceptance of a node, when and only when that node
+    /// turns out to have no children.
+    fn update_epsilon(
+        &mut self,
+        node_id: usize,
+        edges: impl Iterator<Item = (Roi, usize)>,
+    ) -> Result<(), Self::Error>;
+
     /// An iterator that iterates all layers that need to be merged.
     type DerIter: Iterator<Item = TwoLayers>;
 
@@ -181,10 +243,10 @@ pub trait Chain: LabelExtGraph<Edge> {
     fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error>;
 
     /// Take the union of all derivatives.
-    fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Edge, usize)>, Self::Error> {
+    fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Roi, usize)>, Self::Error> {
         // REVIEW: Find a way to avoid allocations.
         Collapsed::<_, Self>::collapse(der_iter, self)
-            .collect::<Result<Vec<(Edge, usize)>, Self::Error>>()
+            .collect::<Result<Vec<(Roi, usize)>, Self::Error>>()
             .map(|mut v| {
                 v.retain(|(_, target)| {
                     *target == 0 || matches!(self.degree(*target), Ok(deg) if deg != 0)
@@ -200,7 +262,15 @@ pub trait Chain: LabelExtGraph<Edge> {
 
         let edges = self.union(der_iter)?;
 
-        let new_index = self.extend(edges)?;
+        let new_index = self.extend(
+            edges
+                .iter()
+                .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, *target))),
+        )?;
+
+        if self.is_empty_node(new_index)? {
+            self.update_epsilon(new_index, edges.into_iter())?;
+        }
 
         self.update_history(new_index);