forest: clone correctly

Now the forest can detect if a node is packed or cloned, and correctly
clones a node in those circumstances.  But it still needs to be
tested.

3 files changed, 12 insertions, 54 deletions

diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs
index 14b7a9f..e88cfc9 100644
--- a/chain/src/atom/default.rs
+++ b/chain/src/atom/default.rs
@@ -429,12 +429,6 @@ impl DefaultAtom {
                                     GrammarError::IndexOutOfBounds(child, accepting_vec.len()),
                                 )?;
 
-                        if nt == 3
-                            && nfa.degree(child).map_err(index_out_of_bounds_conversion)? == 0
-                        {
-                            println!("accepting = {accepting}");
-                        }
-
                         if let Some((_, old_accepting)) = terminals_map.get_mut(&t) {
                             *old_accepting = *old_accepting || accepting;
                         } else {
@@ -455,40 +449,13 @@ impl DefaultAtom {
                 }
             }
 
-            if nt == 3 {
-                println!("map = {terminals_map:?}");
-            }
-
             for (t, (set, accepting)) in terminals_map.into_iter() {
-                let new_index = nfa
-                    .extend(set.into_iter())
-                    .map_err(index_out_of_bounds_conversion)?;
+                let new_index = nfa.extend(set).map_err(index_out_of_bounds_conversion)?;
 
                 if accepting_vec.get(new_index).is_none() {
                     #[cfg(debug_assertions)]
                     assert_eq!(new_index, accepting_vec.len());
 
-                    // let mut updated = false;
-                    // let nfa_len = nfa.nodes_len();
-
-                    // 'label_loop: for (label, target_iter) in nfa
-                    //     .labels_of(new_index)
-                    //     .map_err(|_| GrammarError::IndexOutOfBounds(new_index, nfa_len))?
-                    // {
-                    //     if label_is_nullable(*label) {
-                    //         for target in target_iter {
-                    //             if *accepting_vec
-                    //                 .get(target)
-                    //                 .ok_or(GrammarError::IndexOutOfBounds(target, nfa_len))?
-                    //             {
-                    //                 updated = true;
-
-                    //                 break 'label_loop;
-                    //             }
-                    //         }
-                    //     }
-                    // }
-
                     accepting_vec.push(accepting);
                 }
 
diff --git a/chain/src/default.rs b/chain/src/default.rs
index b9d7fe6..22befff 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -10,10 +10,7 @@ use crate::atom::{Atom, DefaultAtom};
 use core::fmt::Display;
 use forest::{default::DefaultForest, Forest};
 use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT};
-#[allow(unused_imports)]
-use graph::{
-    labelled::DLGBuilder, Builder, DLGraph, Graph, LabelExtGraph, LabelGraph, ParentsGraph,
-};
+use graph::{labelled::DLGBuilder, Builder, DLGraph, Graph, LabelExtGraph, LabelGraph};
 
 use std::collections::{HashMap as Map, TryReserveError};
 
@@ -156,11 +153,13 @@ impl Iterator for DerIter {
                         None
                     }
                 } else {
-                    self.index = DerIterIndex::Single(0);
+                    // If the zero-th element is present, we will
+                    // advance the index to one; if it is not present,
+                    // we will stop iteration.  In each case we can
+                    // safely set the index to one.
+                    self.index = DerIterIndex::Single(1);
 
                     if let Some((edge, to)) = self.singles.first() {
-                        self.index = DerIterIndex::Single(1);
-
                         Some(TwoLayers::One(*edge, *to))
                     } else {
                         None
@@ -776,15 +775,7 @@ mod test_chain {
 
         println!("repeating {repeat_times} times");
 
-        let input = {
-            let mut result = Vec::with_capacity(input_template.len() * repeat_times);
-
-            for _ in 0..repeat_times {
-                result.extend(input_template.iter().copied());
-            }
-
-            result
-        };
+        let input = input_template.repeat(repeat_times);
 
         let start = std::time::Instant::now();
 
diff --git a/chain/src/lib.rs b/chain/src/lib.rs
index 91c37f7..a3d420b 100644
--- a/chain/src/lib.rs
+++ b/chain/src/lib.rs
@@ -131,6 +131,7 @@ where
                         Ok(new) => new,
                         Err(error) => {
                             // Prevent further iterations.
+                            self.stop = true;
 
                             return Some(Err(error.into()));
                         }
@@ -157,8 +158,7 @@ pub trait Chain: LabelExtGraph<Edge> {
 
     /// Represents the language that is present after we parse the
     /// empty string, that is the initial configuration of the
-    /// language.  This may or may not be different from what
-    /// `Default::default` gives.
+    /// language.
     fn unit(atom: Self::Atom) -> Result<Self, Self::Error>;
 
     /// Return true if and only if the language contains the empty
@@ -171,7 +171,7 @@ pub trait Chain: LabelExtGraph<Edge> {
     /// An iterator that iterates all layers that need to be merged.
     type DerIter: Iterator<Item = TwoLayers>;
 
-    /// Take the derivative by a terminal symbol at position `POS`.
+    /// Take the derivative by a terminal `t` at position `pos`.
     fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error>;
 
     /// Take the union of all derivatives.
@@ -187,7 +187,7 @@ pub trait Chain: LabelExtGraph<Edge> {
 
         let edges = self.union(der_iter)?;
 
-        let new_index = self.extend(edges.into_iter())?;
+        let new_index = self.extend(edges)?;
 
         self.update_history(new_index);