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, 124 insertions, 0 deletions

diff --git a/grammar/src/label.rs b/grammar/src/label.rs
new file mode 100644
index 0000000..58eaddc
--- /dev/null
+++ b/grammar/src/label.rs
@@ -0,0 +1,124 @@
+//! This file implements a type of labels that could be used as the
+//! labels of a parse forest.
+
+use super::*;
+
+/// The actual label of a grammar label.
+#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub enum GrammarLabelType {
+    /// A terminal or a non-terminal.
+    TNT(TNT),
+    /// A rule position.
+    Rule(usize),
+}
+
+impl GrammarLabelType {
+    /// Return the name of this label with the help of the associated
+    /// grammar.
+    pub fn name(&self, grammar: &Grammar) -> Result<String, Error> {
+        match self {
+            Self::TNT(tnt) => grammar.name_of_tnt(*tnt),
+            Self::Rule(pos) => grammar.rule_pos_to_string(*pos),
+        }
+    }
+}
+
+/// The label to be used in a forest.
+#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
+pub struct GrammarLabel {
+    /// The actual label.
+    label: GrammarLabelType,
+    /// The start in the input that this label correponds to.
+    start: usize,
+    /// The end in the input that this label correponds to.
+    end: Option<usize>,
+    /// A node in the forest might be a packed node.
+    packed_p: bool,
+}
+
+impl core::fmt::Display for GrammarLabel {
+    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+        // Simply displaying this without the help of a grammar is not
+        // of much help, so we just use the debug method to cheat,
+        // haha.
+
+        write!(f, "{:?}", self)
+    }
+}
+
+impl GrammarLabel {
+    /// Construct a new label.
+    pub fn new(label: GrammarLabelType, start: usize) -> Self {
+        let end = None;
+        let packed_p = false;
+
+        Self {
+            label,
+            start,
+            end,
+            packed_p,
+        }
+    }
+
+    /// Return the end in the input.
+    pub fn end(&self) -> Option<usize> {
+        self.end
+    }
+
+    /// Return the start in the input.
+    pub fn start(&self) -> usize {
+        self.start
+    }
+
+    /// Return the actual label.
+    pub fn label(&self) -> GrammarLabelType {
+        self.label
+    }
+
+    /// Update the end.
+    pub fn set_end(&mut self, end: usize) {
+        self.end = Some(end);
+    }
+
+    /// Check whether the node is a packed node.
+    pub fn is_packed(&self) -> bool {
+        self.packed_p
+    }
+
+    /// Update the packed status.
+    pub fn set_packed_p(&mut self, packed_p: bool) {
+        self.packed_p = packed_p;
+    }
+
+    /// Return a string description with the help of the associated
+    /// grammar.
+    pub fn to_string(&self, grammar: &Grammar) -> Result<String, Error> {
+        // REVIEW: It needs at least 34 bytes, so we just double it.
+        // Of course we can also calculate the length exactly, but
+        // this can be postponed till later.
+        let mut s = String::with_capacity(68);
+        s.push_str("a ");
+
+        if self.is_packed() {
+            s.push_str("packed ");
+        } else {
+            s.push_str("normal ");
+        }
+
+        s.push_str("node labelled ");
+
+        s.push_str(&self.label().name(grammar)?);
+
+        s.push_str(" from ");
+
+        s.push_str(&format!("{} ", self.start()));
+
+        if let Some(end) = self.end() {
+            s.push_str(&format!("to {end}"));
+        } else {
+            s.push_str("onwards");
+        }
+
+        Ok(s)
+    }
+}