From 5a40d2cb79a791a46a579fdf6532e1b49053e96c Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Tue, 18 Jul 2023 16:26:54 +0800
Subject: Fix the bug of incorrectly setting the end of forest nodes

Previously when generating a fragment of the forest corresponding to
the expansion of a non-terminal by a terminal, we incorrectly set the
end of every node within it to be one plus the start, if the expansion
happens due to a reduction.

Now this mistake is fixed and the ending positions are correctly set.
---
 chain/src/item/default/mod.rs | 95 ++++++++++++++++++++++++++++++++++---------
 1 file changed, 76 insertions(+), 19 deletions(-)

(limited to 'chain/src/item/default')

diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 7369c6f..5971985 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -3,7 +3,7 @@
 //! forest.
 
 use super::*;
-use crate::atom::default::DefaultAtom;
+use crate::atom::{default::DefaultAtom, Atom};
 use grammar::{GrammarLabel, GrammarLabelType, TNT};
 use graph::{
     builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, LabelGraph, PLGraph, RedirectGraph,
@@ -1174,11 +1174,82 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
     /// Set the position of every node.
     ///
     /// If ALLP is non-nil or if the node is a terminal node, also set
-    /// the ending position.
-    pub(crate) fn set_pos(&mut self, pos: usize, allp: bool) -> Result<(), Error> {
+    /// the ending position whereever reasonable.
+    pub(crate) fn set_pos(
+        &mut self,
+        atom: &DefaultAtom,
+        pos: usize,
+        allp: bool,
+    ) -> Result<(), Error> {
         let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
 
-        for node in 0..builder.nodes_len() {
+        let nodes_len = builder.nodes_len();
+
+        if !allp {
+            for node in 0..nodes_len {
+                let label = builder
+                    .vertex_label(node)?
+                    .ok_or(Error::NodeNoLabel(node))?;
+
+                let mut label_label = label.label();
+
+                label_label.set_start(pos);
+
+                let new_label = ForestLabel::new(label_label, label.status);
+
+                builder.set_label(node, new_label)?;
+            }
+
+            return Ok(());
+        }
+
+        // We assign every node to be open first, and then start from
+        // any terminal node and assign them to be closed, then their
+        // parents are rules.  If those rules are accepting, we assign
+        // the rules and the parents of rules to be closed, and so on
+        // and so forth.
+        //
+        // We need to test this behaviour, though.
+
+        let mut closed_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();
+
+        let mut closed_stack: Vec<usize> = Vec::with_capacity(nodes_len);
+
+        for (node, closed_nodes_ptr) in (0..nodes_len).zip(closed_nodes.iter_mut()) {
+            let label = builder
+                .vertex_label(node)?
+                .ok_or(Error::NodeNoLabel(node))?;
+
+            if matches!(label.label().label().tnt(), Some(TNT::Ter(_))) {
+                *closed_nodes_ptr = true;
+                closed_stack.push(node);
+            }
+        }
+
+        while let Some(node) = closed_stack.pop() {
+            for parent in builder.parents_of(node)?.map(|p| p.node()) {
+                *closed_nodes
+                    .get_mut(parent)
+                    .ok_or(Error::IndexOutOfBounds(parent, nodes_len))? = true;
+
+                let label = builder
+                    .vertex_label(parent)?
+                    .ok_or(Error::NodeNoLabel(parent))?;
+
+                if let Some(rule) = label.label().label().rule() {
+                    if atom
+                        .is_accepting(2 * rule + 1)
+                        .map_err(|_| Error::IndexOutOfBounds(2 * rule + 1, atom.accepting_len()))?
+                    {
+                        closed_stack.push(parent);
+                    }
+                } else {
+                    closed_stack.push(parent);
+                }
+            }
+        }
+
+        for (node, closed_p) in (0..nodes_len).zip(closed_nodes.iter().copied()) {
             let label = builder
                 .vertex_label(node)?
                 .ok_or(Error::NodeNoLabel(node))?;
@@ -1187,22 +1258,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
 
             label_label.set_start(pos);
 
-            if allp || matches!(label_label.label().tnt(), Some(TNT::Ter(_))) {
+            if closed_p {
                 label_label.set_end(pos + 1);
-            } else if builder.degree(node)? == 1 && label_label.label().rule().is_some() {
-                let child = builder.children_of(node)?.next().unwrap();
-
-                if matches!(
-                    builder
-                        .vertex_label(child)?
-                        .ok_or(Error::NodeNoLabel(child))?
-                        .label()
-                        .label()
-                        .tnt(),
-                    Some(TNT::Ter(_))
-                ) {
-                    label_label.set_end(pos + 1);
-                }
             }
 
             let new_label = ForestLabel::new(label_label, label.status);
-- 
cgit v1.2.3-18-g5258