summaryrefslogtreecommitdiff
path: root/chain/src/item/genins.rs
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src/item/genins.rs')
-rw-r--r--chain/src/item/genins.rs494
1 files changed, 370 insertions, 124 deletions
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<GrammarLabelType> = 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<ForestLabel<GrammarLabel>> {
/// 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<DefaultForest<ForestLabel<GrammarLabel>>>,
- atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator,
+ atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator + Clone,
atom: &DefaultAtom,
- ) -> Result<PaSe, Error> {
- let fragment = fragment.borrow();
+ ) -> Result<PaVi, Error> {
+ 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<Parent> = {
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<ForestLabel<GrammarLabel>> {
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<ForestLabel<GrammarLabel>> {
.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<ForestLabel<GrammarLabel>> {
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<ForestLabel<GrammarLabel>> {
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::<Vec<_>>(),
);
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<ForestLabel<GrammarLabel>> {
}
}
- // 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<ForestLabel<GrammarLabel>> {
}
};
// 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<ForestLabel<GrammarLabel>> {
#[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<DefaultAtom>,
- forest: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
- ) -> Result<(), Box<dyn std::error::Error>> {
- 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<dyn std::error::Error>> {
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);
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-09-19 21:32:57 +0000