chain: a prototype is added.

I have an ostensibly working prototype now.

Further tests are needed to make sure that the algorithm meets the
time complexity requirement, though.

1 files changed, 79 insertions, 4 deletions

diff --git a/grammar/src/lib.rs b/grammar/src/lib.rs
index 297cb66..50a2b9b 100644
--- a/grammar/src/lib.rs
+++ b/grammar/src/lib.rs
@@ -320,11 +320,39 @@ impl Grammar {
         self.accumulators.last().copied().unwrap_or(0)
     }
 
+    /// Return an element of the accumulator.
+    #[inline]
+    pub fn nth_accumulator(&self, n: usize) -> Result<usize, Error> {
+        self.accumulators
+            .get(n)
+            .copied()
+            .ok_or_else(|| Error::IndexOutOfBounds(n, self.total()))
+    }
+
+    /// Return the index of the rules a rule position belongs to.
+    #[inline]
+    pub fn get_rule_num(&self, pos: usize) -> Result<usize, Error> {
+        let mut result = None;
+
+        for (index, accumulator) in self.accumulators.iter().copied().skip(1).enumerate() {
+            if accumulator > pos {
+                result = Some(index);
+                break;
+            }
+        }
+
+        if let Some(n) = result {
+            Ok(n)
+        } else {
+            Err(Error::IndexOutOfBounds(pos, self.total()))
+        }
+    }
+
     /// Query if a position is the starting position of a
     /// non-terminal.  If it is, return the non-terminal, else return
     /// `None` .
     #[inline]
-    pub fn is_nt_start_in_nfa_p(&self, pos: usize) -> Option<usize> {
+    pub fn get_nt_start_in_nfa(&self, pos: usize) -> Option<usize> {
         for (index, accumulator) in self.accumulators.iter().copied().enumerate() {
             let shifted_accumulator = accumulator << 1;
 
@@ -456,7 +484,7 @@ impl Grammar {
             }
         }
 
-        Ok(self.expansion_map.get(&(pos1, pos2)).map(|v| &v[..]))
+        Ok(self.expansion_map.get(&(pos1, pos2)).map(|v| v.as_ref()))
     }
 
     // REVIEW: Do we have a better way to record expansion information
@@ -483,7 +511,11 @@ impl Grammar {
         &mut self,
         two_edges: TwoEdges<LabelType<TNT>>,
     ) -> LabelType<TNT> {
+        #[cfg(debug_assertions)]
         let (first_source, first_target, first_label) = two_edges.first_edge();
+        #[cfg(not(debug_assertions))]
+        let (first_source, _, first_label) = two_edges.first_edge();
+
         let (second_source, second_target, second_label) = two_edges.second_edge();
 
         #[cfg(debug_assertions)]
@@ -501,11 +533,11 @@ impl Grammar {
         // that is to say, the source of the second edge is the
         // starting edge of a non-terminal.
 
-        let mut left_p = first_label.get_left_p() || second_label.get_left_p();
+        let mut left_p = first_label.is_left_p() || second_label.is_left_p();
 
         // Record left-linear expansion information.
 
-        if let Some(second_nt) = self.is_nt_start_in_nfa_p(second_source) {
+        if let Some(second_nt) = self.get_nt_start_in_nfa(second_source) {
             left_p = true;
 
             if !self
@@ -554,12 +586,55 @@ impl Grammar {
             .ok_or(Error::IndexOutOfBounds(non_terminal, self.non.len()))?
             .iter())
     }
+
+    /// Return a string describing a rule position.
+    pub fn rule_pos_to_string(&self, pos: usize) -> Result<String, Error> {
+        let rule_num = {
+            let mut result = None;
+
+            for (index, accumulator) in self.accumulators.iter().copied().skip(1).enumerate() {
+                if accumulator > pos {
+                    result = Some(index);
+                    break;
+                }
+            }
+
+            if let Some(n) = result {
+                n
+            } else {
+                return Err(Error::IndexOutOfBounds(pos, self.total()));
+            }
+        };
+
+        assert!(rule_num < self.rules.len());
+
+        let display_tnt = |tnt| self.name_of_tnt(tnt).unwrap_or_else(|e| format!("{e}"));
+
+        Ok(self
+            .rules
+            .get(rule_num)
+            .unwrap()
+            .regex
+            .to_string_with_dot(
+                display_tnt,
+                if rule_num == 0 {
+                    pos
+                } else {
+                    pos - self.accumulators.get(rule_num - 1).copied().unwrap()
+                },
+            )
+            .unwrap())
+    }
 }
 
 pub mod first_set;
 
 pub mod left_closure;
 
+pub mod label;
+
+pub use label::{GrammarLabel, GrammarLabelType};
+
 impl Display for Grammar {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         assert_eq!(self.non.len(), self.rules.len());