summaryrefslogtreecommitdiff
path: root/chain
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-07-21 11:43:53 +0800
committerJSDurand <mmemmew@gmail.com>2023-07-21 11:43:53 +0800
commit081e3d2ed8d3f9b4e4d6fd864283a4230e09b25a (patch)
tree3bc77a546c83f010e9ab4b439d492b15ee9bfd9d /chain
parent5bb59bb5b944c380f762858e1662a2a17f41677c (diff)
chain/default: Remove the annoying node whenever plausible.
The chain-rule machine needs a place-holder node at the beginning. But afterwards that node is pure annoyance and disturbs the functioning of the machine. Consequently I removed that node whenever the right time comes. This seems to fix some other bugs. It is reasonable: the presence of that bogus node is just noise to the machine and error-prone.
Diffstat (limited to 'chain')
-rw-r--r--chain/src/default.rs128
1 files changed, 119 insertions, 9 deletions
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 2f6311c..97dbfa3 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -365,7 +365,7 @@ impl Chain for DefaultChain {
let initial_nullable = atom
.is_nullable(START_NONTERMINAL)
- .map_err(|_| Error::IndexOutOfBounds(0, atom.non_num()))?;
+ .map_err(|_| Error::IndexOutOfBounds(START_NONTERMINAL, atom.non_num()))?;
builder.add_edge(
first,
@@ -569,6 +569,21 @@ impl Chain for DefaultChain {
Ok(accepting)
}
+ if !no_item
+ && self.forest.nodes_len() > 2
+ && matches!(self.forest.degree(1), Ok(d) if d > 0)
+ {
+ // dbg!(self.forest.vertex_label(1)?, self.atom.empty());
+ match self.forest.vertex_label(1) {
+ Ok(Some(label)) => {
+ if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) {
+ self.forest.remove_node(1)?;
+ }
+ }
+ _ => {}
+ }
+ }
+
let mut der_iter = DerIter::default();
let mut accepting_pavi: HashSet<PaVi> = HashSet::new();
@@ -813,9 +828,91 @@ impl Chain for DefaultChain {
dbg!(root_degree, root_label);
+ // First perform reduction.
+
+ let _ = self.forest.print_viz("forest before reduction.gv");
+
+ // self.forest.reduction(root, pos, ter, &self.atom, true)?;
+
// REVIEW: Why nodes?
let mut nodes = Vec::with_capacity(root_degree);
+ // let nodes_len = self.forest.nodes_len();
+
+ // let mut stack: Vec<(usize, ForestLabel<GrammarLabel>)> = Vec::with_capacity(nodes_len);
+ // let mut visited: Vec<_> = std::iter::repeat(false).take(nodes_len).collect();
+
+ // macro_rules! visited {
+ // ($node: expr) => {
+ // visited.get($node).copied() == Some(true)
+ // };
+ // }
+
+ // macro_rules! visit {
+ // ($node: expr) => {
+ // *visited
+ // .get_mut($node)
+ // .ok_or(Error::IndexOutOfBounds($node, nodes_len))? = true;
+ // };
+ // }
+
+ // stack.push((root, root_label));
+
+ // while let Some((top, top_label)) = stack.pop() {
+ // if top_label.is_packed() {
+ // visit!(top);
+
+ // for clone in self.forest.children_of(top)? {
+ // let cloned_label = self
+ // .forest
+ // .vertex_label(clone)?
+ // .ok_or(Error::NodeNoLabel(clone))?;
+ // stack.push((clone, cloned_label));
+ // }
+ // } else if top_label.clone_index().is_some() {
+ // let visited = visited!(top);
+
+ // if visited {
+ // // every child should have been processed
+
+ // if top_label.label().end().is_some() {
+ // continue;
+ // }
+
+ // for child in self.forest.children_of(top)? {
+ // let child_label = self
+ // .forest
+ // .vertex_label(child)?
+ // .ok_or(Error::NodeNoLabel(child))?;
+
+ // if child_label.label().end().is_none() {
+ // continue;
+ // }
+ // }
+
+ // } else {
+ // visit!(top);
+
+ // stack.push((top, top_label));
+
+ // for child in self.forest.children_of(top)? {
+ // if visited!(child) {
+ // continue;
+ // }
+
+ // let child_label = self
+ // .forest
+ // .vertex_label(child)?
+ // .ok_or(Error::NodeNoLabel(child))?;
+
+ // stack.push((child, child_label));
+ // }
+ // }
+ // } else {
+ // //
+ // }
+ // }
+
if root_label.is_packed() {
let mut all_completed_clones = Vec::with_capacity(root_degree);
@@ -884,11 +981,15 @@ impl Chain for DefaultChain {
nodes.push(self.forest.reduction(root, pos, ter, &self.atom, true)?);
}
- dbg!(&nodes);
+ // dbg!(&nodes);
- // self.forest
- // .print_viz("forest before extraction.gv")
- // .unwrap();
+ println!("printing grammar");
+ println!("{}", &(*self.atom));
+ self.atom.print_nullables();
+ self.atom.print_virtual();
+ let _ = item::default::print_labels(&self.atom, &self.forest);
+
+ let _ = self.forest.print_viz("forest before extraction.gv");
result = self.forest.extract(pos)?;
@@ -1066,11 +1167,14 @@ mod test_chain {
let no_item = false;
- let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 1, 0, 1];
+ let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 0, 1, 4, 2, 2, 1];
+
+ let input_len = input.len();
- let to_print = std::fs::metadata("output/").is_ok();
+ // let to_print = std::fs::metadata("output/").is_ok();
+ let to_print = false;
- for (pos, t) in input.iter().copied().enumerate().take(2) {
+ for (pos, t) in input.iter().copied().enumerate().take(input_len) {
chain.chain(t, pos, no_item)?;
if to_print {
chain.forest().print_viz(&format!("forest {pos}.gv"))?;
@@ -1078,7 +1182,13 @@ mod test_chain {
dbg!(pos, t);
}
- item::default::print_labels(&chain.atom, &chain.forest)?;
+ // let _ = chain.forest.print_viz("forest before extraction.gv");
+
+ let extracted = chain.end_of_input(input_len, input[input_len - 1])?;
+
+ let _ = extracted.print_viz("extracted forest.gv");
+
+ // item::default::print_labels(&chain.atom, &chain.forest)?;
Ok(())
}