From 265ff8f87dc7392fdf701f811eb2bf54d7bc6678 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 3 Feb 2023 10:52:35 +0800
Subject: Finally produced the first correct forest

Finally the prototype parser has produced the first correct forest.
It is my first time to generate a correct forest, in fact, ever since
the beginning of this project.
---
 chain/src/default.rs | 82 ++++++++++++++++++----------------------------------
 1 file changed, 28 insertions(+), 54 deletions(-)

(limited to 'chain/src/default.rs')

diff --git a/chain/src/default.rs b/chain/src/default.rs
index 77a64ca..5e94623 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -8,7 +8,8 @@
 use super::*;
 use crate::atom::{Atom, DefaultAtom};
 use crate::item::{
-    default::DefaultForest, generate_fragment, Forest, ForestLabel, ForestLabelError,
+    default::DefaultForest, generate_fragment, genins::virtual_generate_fragment, Forest,
+    ForestLabel, ForestLabelError,
 };
 use core::fmt::Display;
 use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT};
@@ -35,6 +36,8 @@ pub enum Error {
     CannotClone(ForestLabelError),
     /// Cannot find a suitable node to plant the new forest fragment.
     CannotPlant,
+    /// Trying to insert an empty item.
+    EmptyItem,
     /// An invalid situation happens.
     Invalid,
 }
@@ -52,6 +55,7 @@ impl Display for Error {
             Self::CannotReserve(e) => write!(f, "cannot reserve memory: {e}"),
             Self::CannotClone(fe) => write!(f, "cannot clone due to {fe}"),
             Self::CannotPlant => write!(f, "cannot plant a new forest fragment"),
+            Self::EmptyItem => write!(f, "trying to insert an empty item"),
             Self::Invalid => write!(f, "invalid"),
         }
     }
@@ -393,7 +397,6 @@ impl Chain for DefaultChain {
             .is_nullable(0)
             .map_err(|_| Error::IndexOutOfBounds(0, atom.non_num()))?;
 
-        // NOTE: Is it really correct to use `Parent::new(0, 0)` here?
         builder.add_edge(
             first,
             root,
@@ -585,15 +588,13 @@ impl Chain for DefaultChain {
                         )?;
                     }
                     Some(Non(non)) => {
-                        let first_fragment =
-                            generate_fragment([atom_moved.into(), Non(non).into()], pos)?;
-
-                        let first_segment_pase = self.forest.insert_item(
-                            *label,
-                            first_fragment,
-                            atom_child_iter.clone(),
-                            &self.atom,
-                        )?;
+                        if !self
+                            .atom
+                            .is_first_of(non, t)
+                            .map_err(index_out_of_bounds_conversion)?
+                        {
+                            continue;
+                        }
 
                         let virtual_node = self
                             .atom
@@ -601,59 +602,30 @@ impl Chain for DefaultChain {
                             .map_err(index_out_of_bounds_conversion)?;
 
                         if let Some(virtual_node) = virtual_node {
+                            let first_fragment =
+                                generate_fragment([atom_moved.into(), Non(non).into()], pos)?;
+
+                            let first_segment_pase = self.forest.insert_item(
+                                *label,
+                                first_fragment,
+                                atom_child_iter.clone(),
+                                &self.atom,
+                            )?;
+
                             let accepting = self
                                 .atom
                                 .is_accepting(virtual_node)
                                 .map_err(index_out_of_bounds_conversion)?;
 
-                            let virtual_fragment = {
-                                // `non` is valid, as checked above
-                                let non_start = self.atom.nth_accumulator(non).unwrap() * 2;
-
-                                let mut result = DefaultForest::default();
-
-                                for (label, child_iter) in self.atom.labels_of(non_start)? {
-                                    if matches!(*label.get_value(),
-                                                Some(Ter(ter)) if ter == t)
-                                    {
-                                        for child in child_iter {
-                                            let mut line: Vec<_> = self
-                                                .atom
-                                                .query_expansion(non_start, child)
-                                                .map_err(index_out_of_bounds_conversion)?
-                                                .iter()
-                                                .copied()
-                                                .flatten()
-                                                .map(|(nt, rule)| [(*rule).into(), Non(*nt).into()])
-                                                .collect();
-
-                                            line.push([label.get_moved().into(), Ter(t).into()]);
-
-                                            let line: Vec<GrammarLabelType> =
-                                                line.into_iter().flatten().collect();
-
-                                            if result.is_empty() {
-                                                result = generate_fragment(line, pos)?;
-                                            } else {
-                                                result.plant(
-                                                    0,
-                                                    generate_fragment(line, pos)?,
-                                                    false,
-                                                )?;
-                                            }
-                                        }
-                                    }
-                                }
-
-                                result
-                            };
+                            let virtual_fragment =
+                                virtual_generate_fragment(&self.atom, non, t, pos)?;
 
                             // NOTE: We only need the PaSe from the
                             // first segment, so we pass an empty
                             // iterator, in which case the passed
                             // label is only used for the PaSe.
                             let virtual_pase = self.forest.insert_item(
-                                Edge::new(0, first_segment_pase, true),
+                                Edge::new(0, first_segment_pase, accepting),
                                 virtual_fragment,
                                 std::iter::empty(),
                                 &self.atom,
@@ -810,8 +782,8 @@ mod test_chain {
         let atom = DefaultAtom::from_grammar(grammar)?;
 
         let mut chain = DefaultChain::unit(atom)?;
-
         chain.chain(3, 00)?;
+        dbg!("hi");
         chain.chain(1, 01)?;
         chain.chain(2, 02)?;
         chain.chain(2, 03)?;
@@ -831,6 +803,8 @@ mod test_chain {
         {
             chain.graph.print_viz("chain.gv")?;
             chain.atom.print_nfa("nfa.gv")?;
+            chain.forest.print_viz("forest.gv")?;
+            item::default::print_labels(&chain.atom, &chain.forest)?;
         }
 
         Ok(())
-- 
cgit v1.2.3-18-g5258