diff options
Diffstat (limited to 'chain/src/default.rs')
| -rw-r--r-- | chain/src/default.rs | 247 |
1 files changed, 129 insertions, 118 deletions
diff --git a/chain/src/default.rs b/chain/src/default.rs index ed63ff4..7de720f 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -11,15 +11,19 @@ use crate::item::{ default::DefaultForest, generate_fragment, genins::index_out_of_bounds_conversion, Forest, ForestLabel, ForestLabelError, }; -use core::fmt::Display; use grammar::{GrammarLabel, GrammarLabelType, START_NONTERMINAL, TNT}; +#[allow(unused_imports)] use graph::{ labelled::DLGBuilder, Builder, DLGraph, Graph, LabelExtGraph, LabelGraph, ParentsGraph, }; +use std::fmt::Display; use graph_macro::Graph; -use std::collections::{HashMap as Map, HashSet, TryReserveError}; +use std::{ + borrow::Borrow, + collections::{HashMap as Map, HashSet, TryReserveError}, +}; /// The errors related to taking derivatives by chain rule. #[non_exhaustive] @@ -399,6 +403,10 @@ impl Chain for DefaultChain { }) } + fn atom(&self) -> &Self::Atom { + self.atom.borrow() + } + fn epsilon(&self) -> Result<bool, Self::Error> { self.accepting_vec .get(self.current) @@ -783,146 +791,119 @@ impl Chain for DefaultChain { Ok(der_iter) } - // FIXME: Do nothing more than to make this at the end of input, - // actually. - // - // This means we only close the expansions at the last accepting - // sources. - // - // As to the remaining still open fragments, they should be - // considered as bugs and should be fixed in the function - // `insert_item` instead. - - fn end_of_input(&mut self) -> Result<(), Self::Error> { - if !matches!(self.epsilon(), Ok(true)) { - return Ok(()); - } - - self.forest.remove_node(1)?; - - let mut stack = Vec::new(); - - dbg!(&self.accepting_sources); + type Item = DefaultForest<ForestLabel<GrammarLabel>>; - // self.forest.print_viz("dbg forest before.gv").unwrap(); + fn end_of_input(&mut self, pos: usize, ter: usize) -> Result<Self::Item, Error> { + let mut result = Default::default(); - for pavi in self.accepting_sources.iter() { - match pavi { - PaVi::Parent(node, _edge, child) => { - // REVIEW: This is a garbage node that has to be - // added when the machine starts. Is there a way - // to avoid this garbage? - if *node == 1 { - continue; - } + let root = if let Some(root) = self.forest.root() { + root + } else { + return Ok(result); + }; - stack.push(*child); - } - PaVi::Virtual(nt, t, node) => { - let node_label = self - .forest - .vertex_label(*node)? - .ok_or(Error::NodeNoLabel(*node))?; + // The 1-th node is a dummy node that should be removed. + assert_ne!(root, 1); - if node_label.label().end().is_none() { - let reduction_fragment = self.atom.generate_virtual_frags(*nt, *t, None); + self.forest.remove_node(1)?; - for frag in reduction_fragment.into_iter().flatten() { - let mut frag = frag.clone(); - frag.set_pos(node_label.label().start(), true)?; + let root_degree = self.forest.degree(root)?; - stack.push(self.forest.plant_at_start(*node, frag)?); - } - } - } - PaVi::Empty => {} - } - } + let root_label = self + .forest + .vertex_label(root)? + .ok_or(Error::NodeNoLabel(root))?; - let forest_nodes_len = self.forest.nodes_len(); - - let mut node_ends: Vec<Vec<usize>> = std::iter::repeat_with(Default::default) - .take(forest_nodes_len) - .collect(); - - // NOTE: Use iterator to avoid checking bounds when accessing - // `node_ends`. - for (node, node_end) in self.forest.nodes().zip(node_ends.iter_mut()) { - if let Some(end) = self - .forest - .vertex_label(node)? - .ok_or(Error::NodeNoLabel(node))? - .label() - .end() - { - node_end.push(end); - } - } + dbg!(root_degree, root_label); - #[derive(Copy, Clone)] - enum StackElement { - Seen(usize), - Unseen(usize), - } + // REVIEW: Why nodes? + let mut nodes = Vec::with_capacity(root_degree); - use StackElement::{Seen, Unseen}; + if root_label.is_packed() { + let mut all_completed_clones = Vec::with_capacity(root_degree); - // maybe we do not need so much space? - let mut stack = Vec::with_capacity(forest_nodes_len); + for clone in self.forest.children_of(root)? { + let mut all_completed = true; - stack.push(Unseen( - self.forest.root().ok_or(Error::IndexOutOfBounds(0, 0))?, - )); + // The last child does not count. + let clone_child_degree_minus_one = std::cmp::max(self.forest.degree(clone)?, 1) - 1; - let mut seen_nodes = HashSet::with_capacity(forest_nodes_len); + // The loop to determine whether or not it is all + // completed, except for the last child. + 'completion_det_loop: for clone_child in self + .forest + .children_of(clone)? + .take(clone_child_degree_minus_one) + { + let clone_child_label = self + .forest + .vertex_label(clone_child)? + .ok_or(Error::NodeNoLabel(clone_child))?; - // depth-first search - while let Some(top) = stack.pop() { - match top { - Seen(top) => { - // Every of its children should be processed - // already. + if clone_child_label.label().end().is_none() { + all_completed = false; - if !node_ends.get(top).unwrap().is_empty() { - continue; + break 'completion_det_loop; } - - let last_index = self.forest.degree(top).unwrap() - 1; - let last_child = self.forest.nth_child(top, last_index)?; - - *node_ends.get_mut(top).unwrap() = node_ends - .get(last_child) - .ok_or(Error::IndexOutOfBounds(last_child, forest_nodes_len))? - .clone(); } - Unseen(top) => { - if seen_nodes.contains(&top) { - continue; - } - seen_nodes.insert(top); - // NOTE: After the above check we can safely unwrap. + if all_completed { + all_completed_clones.push(clone); + } + } - let mut top_no_children = true; + if all_completed_clones.is_empty() { + // Nothing to do + return Ok(result); + } - for child in self.forest.children_of(top).unwrap() { - if top_no_children { - stack.push(Seen(top)); - } + for clone in all_completed_clones { + nodes.push( + self.forest + .reduction(clone, pos, ter, self.atom.borrow(), true)?, + ); + } + } else if root_label.clone_index().is_some() { + panic!( + "If the root of the forest is cloned, \ + the root should be changed to the packed node." + ); + } else { + // The last child does not count. + let root_degree_minus_one = std::cmp::max(root_degree, 1) - 1; - top_no_children = false; + dbg!(root_degree_minus_one); - stack.push(Unseen(child)); - } + // The loop to determine whether or not it is all + // completed, except for the last child. + for root_child in self.forest.children_of(root)?.take(root_degree_minus_one) { + let root_child_label = self + .forest + .vertex_label(root_child)? + .ok_or(Error::NodeNoLabel(root_child))?; - if !top_no_children { - continue; - } + if root_child_label.label().end().is_none() { + return Ok(result); } } + + nodes.push( + self.forest + .reduction(root, pos, ter, self.atom.borrow(), true)?, + ); } - Ok(()) + dbg!(&nodes); + + // self.forest + // .print_viz("forest before extraction.gv") + // .unwrap(); + + result = self.forest.extract(pos)?; + + // result.print_viz("extracted forest.gv").unwrap(); + + Ok(result) } } @@ -1051,7 +1032,7 @@ mod test_chain { chain.chain(0, 12, no_item)?; if !no_item { - chain.end_of_input()?; + let _output = chain.end_of_input(13, 0)?; chain.forest.print_viz("forest.gv")?; chain.graph.print_viz("chain.gv")?; @@ -1079,6 +1060,36 @@ mod test_chain { } #[test] + fn test_assumption() -> Result<(), Box<dyn std::error::Error>> { + use grammar::Grammar; + + dbg!(); + let grammar_str = std::fs::read_to_string( + "/Users/durand/Desktop/Centre/A propos de programmes/Rust/rep/grammar/abnf grammars/test.abnf", + ) + .unwrap(); + dbg!(); + let grammar: Grammar = grammar_str.parse()?; + + let atom = DefaultAtom::from_grammar(grammar)?; + let mut chain = DefaultChain::unit(atom)?; + + let no_item = false; + + let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 1, 0, 1]; + + for (pos, t) in input.iter().copied().enumerate().take(2) { + chain.chain(t, pos, no_item)?; + chain.forest().print_viz(&format!("forest {pos}.gv"))?; + dbg!(pos, t); + } + + item::default::print_labels(&chain.atom, &chain.forest)?; + + Ok(()) + } + + #[test] fn test_ambiguity() -> Result<(), Box<dyn std::error::Error>> { if std::fs::metadata("debug.log").is_ok() { std::fs::remove_file("debug.log")?; @@ -1125,7 +1136,7 @@ mod test_chain { chain.chain(1, 4, no_item)?; if !no_item { - // chain.end_of_input()?; + let _output = chain.end_of_input(5, 1)?; chain.forest.print_viz("forest.gv")?; // chain.forest.print_closed_viz("closed.gv")?; } |