From 8f8d3d1a3c276be4be2e5d2e767ada564c47279a Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Fri, 13 Jan 2023 14:26:28 +0800
Subject: forest seems to be completed

I seem to have finished the implementation of forests.  Now it remains
the implementation of the chain-rule machine, of which I have a rough
plan now.
---
 grammar/Cargo.toml                             |  3 ++
 grammar/src/lib.rs                             | 15 +++++++++-
 grammar/src/tests/test_grammar_left_closure.rs | 38 +++++++++++++++++---------
 3 files changed, 42 insertions(+), 14 deletions(-)

(limited to 'grammar')

diff --git a/grammar/Cargo.toml b/grammar/Cargo.toml
index 20c4b48..793ab5a 100644
--- a/grammar/Cargo.toml
+++ b/grammar/Cargo.toml
@@ -12,6 +12,9 @@ default = []
 # some grammars for testing.
 test-helper = []
 
+# This flag controls whether to print GraphViz files during testing.
+test-print-viz = []
+
 [dependencies]
 nfa = { path = "../nfa" }
 graph = { path = "../graph" }
diff --git a/grammar/src/lib.rs b/grammar/src/lib.rs
index 627ae6f..297cb66 100644
--- a/grammar/src/lib.rs
+++ b/grammar/src/lib.rs
@@ -462,6 +462,19 @@ impl Grammar {
     // REVIEW: Do we have a better way to record expansion information
     // than to compute the transitive closure?
 
+    // REVIEW: We need a way to eliminate those left-linearly expanded
+    // edges whose labels had already been considered, and we need to
+    // preserve the transition of the `left_p` property at the same
+    // time.
+    //
+    // Maybe we could decide to delete those edges in the
+    // `remove_predicate`?  But we cannot access the states of NFA in
+    // that predicate, in the current design, thus we need to refactor
+    // some codes, it seems: we need a way to "compactify" an NFA, by
+    // a key function, in such a way that if two entries have the same
+    // key (determined by the key function), then only one, determined
+    // by another function, remains in the NFA.
+
     /// A transformer of labels to be fed into
     /// [`closure`][nfa::default::nfa::DefaultNFA::closure], with the
     /// predicate that returns true if and only if the label of the
@@ -483,7 +496,7 @@ impl Grammar {
         }
 
         // Compute if this is from left-linear expansion: it is so if
-        // and only if one if either the edges comes from left-linear
+        // and only if either one of the edges comes from left-linear
         // expansion or we are moving across a non-terminal expansion,
         // that is to say, the source of the second edge is the
         // starting edge of a non-terminal.
diff --git a/grammar/src/tests/test_grammar_left_closure.rs b/grammar/src/tests/test_grammar_left_closure.rs
index 003c211..ffc7c0f 100644
--- a/grammar/src/tests/test_grammar_left_closure.rs
+++ b/grammar/src/tests/test_grammar_left_closure.rs
@@ -33,9 +33,6 @@ fn test_regex() -> Result<(), Box<dyn std::error::Error>> {
     Ok(())
 }
 
-// We ignore this test by default as it is possibly involved with
-// printing to a graphviz file.
-#[ignore]
 #[test]
 fn test_nfa() -> Result<(), Box<dyn std::error::Error>> {
     let mut grammar = new_notes_grammar()?;
@@ -69,19 +66,22 @@ fn test_nfa() -> Result<(), Box<dyn std::error::Error>> {
     grammar
         .left_closure_to_nfa(&closure)
         .map(|_| ())
-        .map_err(Into::into)
+        .map_err(Into::<Box<dyn std::error::Error>>::into)?;
 
     // let _nfa = grammar.left_closure_to_nfa(&closure)?;
 
-    // writeln!(lock, "Not printing nfa to nfa.gv")?;
+    #[cfg(features = "test-print-viz")]
+    {
+        writeln!(lock, "Not printing nfa to nfa.gv")?;
 
-    // nfa.print_viz("nfa.gv").map_err(Into::into)
+        nfa.print_viz("nfa.gv")
+            .map_err(Into::<Box<dyn std::error::Error>>::into)?;
+    }
 
-    // Ok(())
+    Ok(())
 }
 
 #[test]
-#[ignore]
 fn test_remove_epsilon() -> Result<(), Box<dyn std::error::Error>> {
     let mut lock = stdout().lock();
 
@@ -123,17 +123,18 @@ fn test_remove_epsilon() -> Result<(), Box<dyn std::error::Error>> {
 
     let mut nfa = grammar.left_closure_to_nfa(&closure)?;
 
+    #[cfg(features = "test-print-viz")]
     nfa.print_viz("nfa_orig.gv")?;
 
     nfa.remove_epsilon(|label| label.get_value().is_none())?;
 
+    #[cfg(features = "test-print-viz")]
     nfa.print_viz("nfa_no_epsilon.gv")?;
 
     Ok(())
 }
 
 #[test]
-#[ignore]
 fn test_remove_dead() -> Result<(), Box<dyn std::error::Error>> {
     let mut grammar = new_paren_grammar()?;
     let closure = new_closure_regex(&mut grammar)?;
@@ -173,9 +174,10 @@ fn test_remove_dead() -> Result<(), Box<dyn std::error::Error>> {
 
     let mut nfa = grammar.left_closure_to_nfa(&closure)?;
 
+    #[cfg(features = "test-print-viz")]
     nfa.print_viz("nfa_orig.gv")?;
 
-    nfa.remove_epsilon(|label| label.get_value().is_none())?;
+    // nfa.remove_epsilon(|label| label.get_value().is_none())?;
 
     let accumulators: HashSet<usize> = accumulators.into_iter().collect();
 
@@ -183,15 +185,22 @@ fn test_remove_dead() -> Result<(), Box<dyn std::error::Error>> {
 
     let grammar_reserve_node = |node| accumulators.contains(&node);
 
+    nfa.closure(
+        |label| label.get_value().is_none(),
+        true,
+        |two_edges| two_edges.second_edge().2,
+        |label| label.get_value().is_none(),
+    )?;
+
     nfa.remove_dead(grammar_reserve_node)?;
 
+    #[cfg(features = "test-print-viz")]
     nfa.print_viz("nfa_no_dead.gv")?;
 
     Ok(())
 }
 
 #[test]
-#[ignore]
 fn test_nulling() -> Result<(), Box<dyn std::error::Error>> {
     // TODO: Test more grammars.
     let mut grammar = new_right_recursive_grammar()?;
@@ -273,9 +282,12 @@ fn test_nulling() -> Result<(), Box<dyn std::error::Error>> {
 
     nfa.remove_dead(grammar_reserve_nodes)?;
 
-    writeln!(lock, "Printing nfa to nfa.gv")?;
+    #[cfg(features = "test-print-viz")]
+    {
+        writeln!(lock, "Printing nfa to nfa.gv")?;
 
-    nfa.print_viz("nfa.gv")?;
+        nfa.print_viz("nfa.gv")?;
+    }
 
     Ok(())
 }
-- 
cgit v1.2.3-18-g5258