From 1a3d346f413325ed37848a6b2526e8e729269833 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Wed, 11 Jan 2023 23:47:26 +0800
Subject: Record left-linear expansion and forest format

Now the grammar will record the left-linear expansions when generating
the nondeterministic finite automaton frmo its rules, and will record
whether an edge in the nondeterministic finite automaton comes from a
left-linear expansion.  The latter is needed because while performing
a chain-rule derivation, we do not need the left-linear expanded
derivations in the "first layer".  This might well have been the root
cause of the bad performance of the previous version of this package.

Also I have figured out how to properly generate and handle parse
forests while manipulating the "chain-rule machine".
---
 graph/src/lib.rs | 31 ++++++++++++++++++++++++++++---
 1 file changed, 28 insertions(+), 3 deletions(-)

(limited to 'graph/src/lib.rs')

diff --git a/graph/src/lib.rs b/graph/src/lib.rs
index 26159c6..6813df3 100644
--- a/graph/src/lib.rs
+++ b/graph/src/lib.rs
@@ -214,12 +214,37 @@ impl<T: Hash + Eq + PartialEq + Clone + Copy + Ord + PartialOrd + Display + Debu
 {
 }
 
+/// We need both the node index of a parent and the edge index of the
+/// child that points to this parent.
+#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
+pub struct Parent(usize, usize);
+
+impl Parent {
+    /// Return the index of the parent node.
+    #[inline]
+    pub fn node(&self) -> usize {
+        self.0
+    }
+
+    /// Return the index of the edge that points to the child.
+    #[inline]
+    pub fn edge(&self) -> usize {
+        self.1
+    }
+
+    /// Construct a parent strucure.
+    #[inline]
+    pub fn new(node: usize, edge: usize) -> Self {
+        Self(node, edge)
+    }
+}
+
 /// A parents-knowing graph can return an iterator of parents for any
 /// node.
 pub trait ParentsGraph: Graph {
     /// The type of an iterator that goes through the parents of a
     /// node.
-    type Iter<'a>: Iterator<Item = usize> + 'a
+    type Iter<'a>: Iterator<Item = Parent> + 'a
     where
         Self: 'a;
 
@@ -340,14 +365,14 @@ mod test_cycle_detection {
 
         let graph = builder.build_ref();
 
-        assert_eq!(graph.contains_cycles()?, true);
+        assert!(!graph.contains_cycles()?);
 
         // Remove the link from the last node to the first node.
         builder.remove_edge(4, 0, |_| true)?;
 
         let graph = builder.build();
 
-        assert_eq!(graph.contains_cycles()?, false);
+        assert!(!graph.contains_cycles()?);
 
         Ok(())
     }
-- 
cgit v1.2.3-18-g5258