Finished the Emacs binding.

Now the binding part is finished.

What remains is a bug encountered when planting a fragment to the
forest which intersects a packed node, which would lead to invalid
forests.  This will also cause problem when planting a packed
fragment, but until now my testing grammars do not produce packed
fragments, so this problem is not encountered yet.

I am still figuring out efficient ways to solve this problem.

1 files changed, 59 insertions, 26 deletions

diff --git a/chain/src/item/reduction.rs b/chain/src/item/reduction.rs
index 89306e6..3c76c1e 100644
--- a/chain/src/item/reduction.rs
+++ b/chain/src/item/reduction.rs
@@ -122,6 +122,9 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// The parameter `ter` is used to fill in segments for virtual
     /// nodes if they are found along the way.
     ///
+    /// The parameter `accept_root` controls whether we want to
+    /// perform reduction on the root.
+    ///
     /// # Errors
     ///
     /// 1. Index out of bounds: some node number is corrupted.
@@ -132,12 +135,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         pos: usize,
         ter: usize,
         atom: &DefaultAtom,
+        accept_root: bool,
     ) -> Result<usize, Error> {
         let mut result = node;
 
         // step 1: Determine if this needs reductions.
 
-        if self.root() == Some(node) {
+        if !accept_root && self.root() == Some(node) {
             return Ok(result);
         }
 
@@ -152,9 +156,30 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             return Ok(result);
         }
 
+        // Data type for representing the status when performing a
+        // search.
+
+        #[derive(PartialEq, Eq, Copy, Clone, Debug)]
+        enum Status {
+            Correct,
+            Incorrect,
+            Visited,
+        }
+
+        impl From<bool> for Status {
+            fn from(value: bool) -> Self {
+                match value {
+                    true => Self::Correct,
+                    false => Self::Incorrect,
+                }
+            }
+        }
+
+        use Status::*;
+
         // step 2: Find descendents that need reductions.
 
-        let mut correct_ends: Map<usize, bool> = Default::default();
+        let mut correct_ends: Map<usize, Status> = Default::default();
 
         let mut order_of_correct_ends: Vec<usize> = Vec::new();
 
@@ -165,7 +190,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
         use std::{borrow::BorrowMut, io::Write};
 
         // Whether or not to write a debug file.
-        let to_write = false;
+        let to_write = true;
 
         if to_write {
             if let Ok(ref mut file) = file.borrow_mut() {
@@ -181,14 +206,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                 }
             }
 
-            if correct_ends.get(&top).is_some() {
+            let old_value = correct_ends.get(&top).copied();
+
+            if matches!(old_value, Some(Correct) | Some(Incorrect)) {
                 continue 'stack_loop;
             }
 
+            correct_ends.insert(top, Visited);
+
             let top_label = self.vertex_label(top)?.ok_or(Error::NodeNoLabel(top))?;
 
             if let Some(end) = top_label.label().end() {
-                correct_ends.insert(top, end == pos);
+                correct_ends.insert(top, (end == pos).into());
 
                 continue 'stack_loop;
             }
@@ -216,8 +245,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
                     'child_loop: for child in self.children_of(top)? {
                         match correct_ends.get(&child).copied() {
-                            Some(true) => {
-                                correct_ends.insert(top, true);
+                            Some(Correct) => {
+                                correct_ends.insert(top, Correct);
 
                                 inserted = true;
                             }
@@ -232,12 +261,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
                     if has_unexplored_children {
                         stack.push(top);
-                        stack.extend(self.children_of(top)?);
+                        stack.extend(
+                            self.children_of(top)?
+                                .filter(|child| correct_ends.get(child).is_none()),
+                        );
                     } else if !inserted {
-                        correct_ends.insert(top, false);
+                        correct_ends.insert(top, Incorrect);
                     }
                 } else {
-                    correct_ends.insert(top, false);
+                    correct_ends.insert(top, Incorrect);
                 }
 
                 continue 'stack_loop;
@@ -245,6 +277,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             if top_label.is_packed() {
                 let mut has_unexplored_children = false;
+                let mut inserted = false;
 
                 if to_write {
                     if let Ok(ref mut file) = file.borrow_mut() {
@@ -255,12 +288,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
                 for child in self.children_of(top)? {
                     match correct_ends.get(&child).copied() {
-                        Some(true) => {
+                        Some(Correct) => {
                             // NOTE: This is not recorded in the
                             // correct orders, as we do not handle
                             // packed nodes directly.
 
-                            correct_ends.insert(top, true);
+                            correct_ends.insert(top, Correct);
+                            inserted = true;
                         }
                         None => {
                             has_unexplored_children = true;
@@ -280,9 +314,12 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
                 if has_unexplored_children {
                     stack.push(top);
-                    stack.extend(self.children_of(top)?);
-                } else if correct_ends.get(&top).is_none() {
-                    correct_ends.insert(top, false);
+                    stack.extend(
+                        self.children_of(top)?
+                            .filter(|child| correct_ends.get(child).is_none()),
+                    );
+                } else if !inserted {
+                    correct_ends.insert(top, Incorrect);
                 }
 
                 continue 'stack_loop;
@@ -309,7 +346,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                             panic!("a terminal node {top} has no ending position?");
                         }
                         Some(TNT::Non(nt)) => {
-                            correct_ends.insert(top, true);
+                            correct_ends.insert(top, Correct);
 
                             self.close_pavi(atom.borrow(), PaVi::Virtual(nt, ter, top), pos)?;
 
@@ -322,7 +359,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
                     Some(end) => end,
                 };
 
-                correct_ends.insert(top, end == pos);
+                correct_ends.insert(top, (end == pos).into());
 
                 if end == pos {
                     order_of_correct_ends.push(top);
@@ -341,10 +378,12 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
             let last_child = self.nth_child(top, last_index)?;
 
             if let Some(child_correctness_value) = correct_ends.get(&last_child).copied() {
-                correct_ends.insert(top, child_correctness_value);
+                if child_correctness_value != Visited {
+                    correct_ends.insert(top, child_correctness_value);
 
-                if child_correctness_value {
-                    order_of_correct_ends.push(top);
+                    if child_correctness_value == Correct {
+                        order_of_correct_ends.push(top);
+                    }
                 }
             } else {
                 stack.extend([top, last_child]);
@@ -375,12 +414,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             #[cfg(debug_assertions)]
             {
-                let label_label_label = label.label().label();
-
-                assert!(label_label_label.rule().is_none());
-
-                assert!(matches!(label_label_label.tnt(), Some(TNT::Non(_))));
-
                 assert!(label.label().end().is_none());
 
                 assert_ne!(degree, 0);