From fbaa420ed550e9c3e7cdc09d4a8ec22bfbd782a6 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Mon, 27 Feb 2023 12:36:41 +0800 Subject: before a major refactor I decide to adopt a new approach of recording and updating item derivation forests. Since this affects a lot of things, I decide to commit before the refactor, so that I can create a branch for that refactor. --- chain/src/item/genins.rs | 494 +++++++++++++++++++++++++++++++++++------------ 1 file changed, 370 insertions(+), 124 deletions(-) (limited to 'chain/src/item/genins.rs') diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 4c51d9a..feb45c6 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -7,19 +7,24 @@ //! semirings later on. use super::*; -use crate::{atom::DefaultAtom, default::Error, item::default::DefaultForest, Edge}; +use crate::{ + atom::{Atom, DefaultAtom}, + default::Error, + item::default::DefaultForest, + Edge, +}; use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT}; -use graph::Graph; +#[allow(unused_imports)] +use graph::{builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, RedirectGraph}; use core::borrow::Borrow; -use std::collections::HashSet as Set; /// Convert an error telling us that an index is out of bounds. /// /// # Panics /// /// The function panics if the error is not of the expected kind. -fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { +pub(crate) fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { match ge { GrammarError::IndexOutOfBounds(index, bound) => Error::IndexOutOfBounds(index, bound), _ => Error::Invalid, @@ -105,11 +110,6 @@ pub fn virtual_generate_fragment( Some(TNT::Ter(ter)) if ter == t) { for child in child_iter { - // #[allow(unused_must_use)] - // { - // dbg!(non_start, child, atom.query_expansion(non_start, child)); - // } - let line: Vec = atom .query_expansion(non_start, child) .map_err(index_out_of_bounds_conversion)? @@ -124,7 +124,15 @@ pub fn virtual_generate_fragment( if result.is_empty() { result = generate_fragment(line, pos)?; } else { - result.plant(0, generate_fragment(line, pos)?, false)?; + let mut new_fragment = generate_fragment(line, pos)?; + + new_fragment.remove_node(0)?; + + new_fragment.set_root(1)?; + + let cloned = result.clone_node(0, 0, false)?; + + result.plant(cloned, new_fragment, false)?; } } } @@ -133,90 +141,313 @@ pub fn virtual_generate_fragment( Ok(result) } +// TODO: Examine `insert_item` again. + impl DefaultForest> { /// Insert an item derivation forest into a recording forest. /// /// We need the help of other things just for finding the correct /// places to insert these item fragments. - pub fn insert_item( + pub(crate) fn insert_item( &mut self, label: Edge, fragment: impl Borrow>>, - atom_child_iter: impl Iterator + ExactSizeIterator, + atom_child_iter: impl Iterator + ExactSizeIterator + Clone, atom: &DefaultAtom, - ) -> Result { - let fragment = fragment.borrow(); + ) -> Result { + let root = if let Some(root) = self.root() { + root + } else { + panic!("the forest must be non-empty when we insert items"); + }; + + let pavi = label.forest_source(); - let pase = label.forest_source(); + let true_source = label.true_source(); + + let fragment = fragment.borrow(); let fragment_root = if let Some(root) = fragment.root() { root } else { - return Err(Error::EmptyItem); + unreachable!("empty item"); }; - let pos = fragment + let fragment_root_label = fragment .vertex_label(fragment_root)? - .ok_or(Error::NodeNoLabel(fragment_root))? - .label() - .start(); + .ok_or(Error::NodeNoLabel(fragment_root))?; + + let pos = fragment_root_label.label().start(); + + if pavi != true_source { + dbg!(label, pos); + + // Completing from true_source up to the pavi + let true_source_node = match true_source { + PaVi::Parent(node, edge) => { + let nth_child = self.nth_child(node, edge)?; + let nth_child_label = self + .vertex_label(nth_child)? + .ok_or(Error::NodeNoLabel(nth_child))?; + + let nth_child_degree = self.degree(nth_child)?; + let nth_child_last = if nth_child_degree > 0 { + nth_child_degree - 1 + } else { + 0 + }; + + if matches!(nth_child_label.label().label().tnt(), Some(TNT::Non(_))) + && !nth_child_label.is_packed() + { + let sploned = self.splone(nth_child, Some(pos), nth_child_last, false)?; + + sploned + } else { + nth_child + } + } + PaVi::Virtual(nt, t, mut node) => { + let node_label_start = self + .vertex_label(node)? + .ok_or(Error::NodeNoLabel(node))? + .label() + .start(); + + let reduction_fragment = atom.generate_virtual_frags(nt, t, None); + + // FIXME: We shall "close" this fragment as well. + + for frag in reduction_fragment.into_iter().flatten() { + let mut frag = frag.clone(); + frag.set_pos(node_label_start)?; + + // NOTE: The function `plant_if_needed` + // assumes that we want to plant the fragment + // as the first child of the node. This + // assumption holds in this case, but not in + // general. + + node = self.plant_if_needed(node, frag)?; + } + + node + } + PaVi::Empty => { + dbg!(); + root + } + }; + + let true_source_pos = self + .vertex_label(true_source_node)? + .ok_or(Error::NodeNoLabel(true_source_node))? + .label() + .start(); + + let top_node = match pavi { + PaVi::Parent(node, edge) => self.nth_child(node, edge)?, + PaVi::Virtual(_nt, _t, _node) => { + dbg!(label); + + self.print_viz("dbg forest.gv").unwrap(); + fragment.print_viz("dbg fragment.gv").unwrap(); + + unreachable!("I do not think this is possible") + } + PaVi::Empty => { + unreachable!("The empty segment should not need to be reduced") + } + }; + + let mut stack = vec![vec![(top_node, 0)]]; + let mut result_stack = Vec::new(); + + while let Some(mut top_stack) = stack.pop() { + let (node, _) = top_stack.pop().unwrap(); + + let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; + + if node_label.is_packed() { + for node in self.children_of(node)? { + let search_child = self.position_search(node, true_source_pos)?; + + if let Some((child, index)) = search_child { + let mut top_stack = top_stack.clone(); + // Fix the previous element + top_stack.push((node, index)); + + if child == true_source_node { + result_stack.push(top_stack); + } else { + top_stack.push((child, 0)); + + stack.push(top_stack); + } + } + } + } else { + let search_child = self.position_search(node, true_source_pos)?; + + if let Some((child, index)) = search_child { + top_stack.push((node, index)); + + if child == true_source_node { + result_stack.push(top_stack); + } else { + top_stack.push((child, 0)); + + stack.push(top_stack); + } + } + } + } + + // FIXME: We have to change the pavi as well, otherwise we + // are going to use the wrong branch for planting later. + + for stack in result_stack { + // dbg!(&stack); + // self.print_viz("dbg forest.gv").unwrap(); + // panic!("test"); + + let mut first_time = true; + + for (node, index) in stack.into_iter().rev() { + if matches!( + self.vertex_label(node)? + .ok_or(Error::NodeNoLabel(node))? + .label() + .label() + .tnt(), + Some(TNT::Non(_)) + ) { + let sploned = self.splone(node, Some(pos), index, false)?; + + if !first_time { + let last_index = self.degree(sploned)? - 1; + + let last_child = self.nth_child(sploned, last_index)?; + + let last_child_label = self + .vertex_label(last_child)? + .ok_or(Error::NodeNoLabel(last_child))? + .label(); + + if last_child_label.end() != Some(pos) { + let closed_label = GrammarLabel::new_closed( + last_child_label.label(), + last_child_label.start(), + pos, + ); + + let closed_label_id = self + .query_label(closed_label.into()) + .expect("last child closed label not found"); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); - // Ensure the last node in the PaSe is a terminal or a + builder.redirect(sploned, last_index, closed_label_id)?; + } + } + + first_time = false; + } + } + } + } + + // Ensure the last node in the PaVi is a terminal or a // non-terminal node, as an extra safety guard during // development. #[cfg(debug_assertions)] { - if let Some(parent) = pase.parent() { - assert!(matches!( - self.vertex_label(self.nth_child(parent.node(), parent.edge())?), - Ok(Some(label)) - if label.label().label().tnt().is_some())); - } else if let Some((_, leaf)) = pase.segment() { - assert!(matches!( - self.vertex_label(leaf), - Ok(Some(label)) - if label.label().label().tnt().is_some())); - } else { - unreachable!("a pase is neither a parent nor a segment"); + match pavi { + PaVi::Parent(node, edge) => { + assert!(matches!( + self.vertex_label(self.nth_child(node, edge)?), + Ok(Some(label)) + if label.label().label().tnt().is_some())); + } + PaVi::Virtual(nt, t, node) => { + if !matches!( + self.vertex_label(node), + Ok(Some(label)) + if matches!( + label.label().label().tnt(), + Some(TNT::Non(_)))) + { + dbg!(node, self.vertex_label(node)?, pavi); + + self.print_viz("dbg forest.gv").unwrap(); + + panic!("assumption fails"); + } + + if nt >= atom.non_num() { + dbg!(); + return Err(Error::IndexOutOfBounds(nt, atom.non_num())); + } + + if t >= atom.ter_num() { + dbg!(); + return Err(Error::IndexOutOfBounds(t, atom.ter_num())); + } + } + PaVi::Empty => {} } } - let mut is_empty_segment = false; + let is_empty_segment = pavi.is_empty(); let mut parents: Vec = { let mut result = Vec::new(); - if let Some(parent) = pase.parent() { - result.push(parent); - } else { - let (root, leaf) = pase.segment().unwrap(); - let mut seen_nodes = Set::new(); + match pavi { + PaVi::Parent(node, edge) => { + result.push(Parent::new(node, edge)); + } + PaVi::Virtual(nt, t, node) => { + let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; - let mut stack = if root == leaf { - // an empty segment means the root - is_empty_segment = true; + for atom_child in atom_child_iter.clone() { + for rule in atom.trace(nt, t, atom_child).into_iter().flatten() { + let virtual_frag = atom.generate_virtual_frags(nt, t, Some(rule)); - result.push(Parent::new(root, 0)); - vec![] - } else { - vec![root] - }; + if let Some(frag) = virtual_frag { + let mut frag = (*frag.get(0).unwrap()).clone(); - while let Some(top) = stack.pop() { - if seen_nodes.contains(&top) { - continue; - } + frag.set_pos(node_label.label().start())?; - seen_nodes.insert(top); + let frag_nodes_len = frag.nodes_len(); - for (index, child) in self.children_of(top)?.enumerate() { - if child == leaf { - result.push(Parent::new(top, index)); - } else { - stack.push(child); + assert!(frag_nodes_len > 1); + + let last_but_one_label = frag + .vertex_label(frag_nodes_len - 2)? + .ok_or(Error::NodeNoLabel(frag_nodes_len - 2))?; + + // NOTE: The function + // `plant_if_needed` assumes that we + // want to plant the fragment as the + // first child of the node. This + // assumption holds in this case, but + // not in general. + + self.plant_if_needed(node, frag)?; + + let rule_label_pos = self + .query_label(last_but_one_label) + .expect("the forest was wrongly planted"); + + result.push(Parent::new(rule_label_pos, 0)); + } } } } + PaVi::Empty => { + result.push(Parent::new(root, 0)); + } } result @@ -251,6 +482,7 @@ impl DefaultForest> { for atom_child in atom_child_iter { // dbg!(label.label(), atom_child); + // Find reduction information. let reduction_info = atom .query_reduction(label.label(), atom_child) @@ -272,7 +504,8 @@ impl DefaultForest> { .label(), GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt ) { - let sploned_node = self.splone(node.node(), Some(pos), node.edge())?; + let sploned_node = + self.splone(node.node(), Some(pos), node.edge(), false)?; node_label = self .vertex_label(sploned_node)? @@ -282,16 +515,15 @@ impl DefaultForest> { let mut parent_iter = self.parents_of(sploned_node)?; #[cfg(debug_assertions)] - { - assert_eq!(parent_iter.len(), 1); - - assert!(self - .vertex_label(sploned_node)? - .ok_or(Error::NodeNoLabel(sploned_node))? - .is_packed()); - } + assert_eq!(parent_iter.len(), 1); node = parent_iter.next().unwrap(); + + #[cfg(debug_assertions)] + assert!(self + .vertex_label(node.node())? + .ok_or(Error::NodeNoLabel(node.node()))? + .is_packed()); } else { node = Parent::new(sploned_node, node.edge()); } @@ -337,19 +569,29 @@ impl DefaultForest> { atom_child, parents, reduction_info, - atom.query_reduction(label.label(), atom_child).unwrap() + atom.query_reduction(label.label(), atom_child).unwrap(), + is_empty_segment, + atom.trace(0, 3, atom_child) + .into_iter() + .flatten() + .collect::>(), ); self.print_viz("dbg forest.gv").unwrap(); #[cfg(test)] - genins_test::print_labels(atom, self.borrow()).unwrap(); + crate::item::default::print_labels(atom, self.borrow()).unwrap(); return Err(Error::CannotPlant); } - for parent in stack.into_iter() { - let sploned_node = self.splone(parent.node(), None, parent.edge())?; + if pos == 4 && matches!(true_source, PaVi::Virtual(_, _, _)) { + dbg!(&stack, reduction_info, true_source, pavi); + self.print_viz(&format!("pos4ib.gv")).unwrap(); + } + + for parent in stack { + let sploned_node = self.splone(parent.node(), None, parent.edge(), false)?; self.plant(sploned_node, fragment, non_empty)?; @@ -357,24 +599,22 @@ impl DefaultForest> { } } - // If the iterator is empty, just plant at the specified - // child. + // If the iterator is empty, assert the fragment has length + // one, and do not plant anything. if !non_empty { - for parent in parents.into_iter() { - let nth_child = self.nth_child(parent.node(), parent.edge())?; - - self.plant(nth_child, fragment, non_empty)?; - - non_empty = true; - } + assert_eq!(fragment.nodes_len(), 1); } let result = if fragment.nodes_len() == 2 { - let root_label = fragment.vertex_label(0)?.unwrap(); - let leaf_label = fragment.vertex_label(1)?.unwrap(); + let root_label = fragment_root_label; + let leaf_label = fragment + .vertex_label(1 - fragment_root)? + .ok_or(Error::NodeNoLabel(1 - fragment_root))?; // it has been planted, so should be safe. - let node = self.query_label(root_label).unwrap(); + let node = self + .query_label(root_label) + .expect("root label was not found"); let edge = { let mut result = None; @@ -394,16 +634,52 @@ impl DefaultForest> { } }; // dbg!(node, edge, root_label, leaf_label); - PaSe::Parent(node, edge) + PaVi::Parent(node, edge) } else { - let root_label = fragment.vertex_label(0)?.unwrap(); - let leaf_label = fragment.vertex_label(fragment.nodes_len() - 1)?.unwrap(); - // dbg!(root_label, leaf_label); - - PaSe::Segment( - self.query_label(root_label).unwrap(), - self.query_label(leaf_label).unwrap(), - ) + assert_eq!( + fragment.nodes_len(), + 1, + "a virtual fragment should consist of a single terminal node." + ); + + let root_label = fragment_root_label; + + let pavi_parent = pavi.parent().expect( + "When we insert a virtual fragment, the forest_source of + the label must be a parent.", + ); + + let nth_child = self.nth_child(pavi_parent.node(), pavi_parent.edge())?; + + let nth_child_label = self + .vertex_label(nth_child)? + .ok_or(Error::NodeNoLabel(nth_child))? + .label() + .label(); + + let error_str = "When we insert a virtual fragment, the \ + forest source of the label must point to \ + a non-terminal node"; + + let nt = match nth_child_label.tnt().expect(error_str) { + TNT::Non(nt) => nt, + _ => { + dbg!(nth_child, nth_child_label); + + panic!("{error_str}"); + } + }; + + let t = match root_label.label().label().tnt().unwrap() { + TNT::Ter(t) => t, + _ => { + dbg!(root_label); + + panic!("a virtual fragment should consist of a single terminal node") + } + }; + + PaVi::Virtual(nt, t, nth_child) }; Ok(result) @@ -413,40 +689,10 @@ impl DefaultForest> { #[cfg(test)] mod genins_test { use super::*; - #[allow(unused_imports)] - use crate::{default::DefaultChain, item::default::leaf, Chain}; + use crate::item::default::leaf; use grammar::test_grammar_helper::*; - pub fn print_labels( - atom: impl Borrow, - forest: impl Borrow>>, - ) -> Result<(), Box> { - let forest = forest.borrow(); - let atom = atom.borrow(); - - for node in forest.nodes() { - let label = forest.vertex_label(node)?; - - if let Some(label) = label { - let label = label.label.label(); - - match label { - GrammarLabelType::TNT(tnt) => { - println!("{tnt} = {}", atom.name_of_tnt(tnt)?); - } - GrammarLabelType::Rule(pos) => { - println!("pos {pos} = {}", atom.rule_pos_string(pos)?); - } - } - } else { - return Err(Error::NodeNoLabel(node).into()); - } - } - - Ok(()) - } - #[test] fn test_generate_fragment() -> Result<(), Box> { let grammar = new_notes_grammar()?; @@ -497,7 +743,7 @@ mod genins_test { 0, )?; - print_labels(&atom, &virtual_fragment)?; + crate::item::default::print_labels(&atom, &virtual_fragment)?; assert_eq!(virtual_fragment, test_fragment); @@ -511,7 +757,7 @@ mod genins_test { let test_fragment = generate_fragment([TNT::Non(3).into(), 38.into(), TNT::Ter(2).into()], 1)?; - print_labels(&atom, &virtual_fragment)?; + crate::item::default::print_labels(&atom, &virtual_fragment)?; assert_eq!(virtual_fragment, test_fragment); -- cgit v1.2.3-18-g5258