From e8ea01319b3a9032a3f4f69f65e9ca96562b87b9 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sun, 22 Jan 2023 11:49:47 +0800 Subject: 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. --- chain/src/atom/default.rs | 35 +---------------------------------- chain/src/default.rs | 23 +++++++---------------- chain/src/lib.rs | 8 ++++---- 3 files changed, 12 insertions(+), 54 deletions(-) (limited to 'chain') 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 { /// 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; /// Return true if and only if the language contains the empty @@ -171,7 +171,7 @@ pub trait Chain: LabelExtGraph { /// An iterator that iterates all layers that need to be merged. type DerIter: Iterator; - /// 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; /// Take the union of all derivatives. @@ -187,7 +187,7 @@ pub trait Chain: LabelExtGraph { 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); -- cgit v1.2.3-18-g5258