summaryrefslogtreecommitdiff
path: root/chain
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-01-22 11:49:47 +0800
committerJSDurand <mmemmew@gmail.com>2023-01-22 11:49:47 +0800
commite8ea01319b3a9032a3f4f69f65e9ca96562b87b9 (patch)
tree674e7337dce0b9433b9ddfe745b0cf82f528d3ec /chain
parent973c789dae479dd8383b0f7f9cfa5f167fdf3d38 (diff)
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.
Diffstat (limited to 'chain')
-rw-r--r--chain/src/atom/default.rs35
-rw-r--r--chain/src/default.rs23
-rw-r--r--chain/src/lib.rs8
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);