diff options
Diffstat (limited to 'chain/src/item/genins.rs')
| -rw-r--r-- | chain/src/item/genins.rs | 155 |
1 files changed, 137 insertions, 18 deletions
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 9ed3b74..43807f8 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -68,7 +68,7 @@ pub fn generate_fragment( } /// Generate a virtual fragment representing the left-linear null -/// closure [nt]^t. +/// closure \[nt\]^t. pub fn virtual_generate_fragment( atom: impl Borrow<DefaultAtom>, nt: usize, @@ -130,12 +130,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let pase = label.forest_source(); - let _fragment_root = if let Some(root) = fragment.root() { + let fragment_root = if let Some(root) = fragment.root() { root } else { return Err(Error::EmptyItem); }; + let pos = fragment + .vertex_label(fragment_root)? + .ok_or(Error::NodeNoLabel(fragment_root))? + .label() + .start(); + // Ensure the last node in the PaSe is a terminal or a // non-terminal node, as an extra safety guard during // development. @@ -236,26 +242,83 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // locate the nodes for reduction_nt in reduction_info.iter().copied().flatten().rev() { - while let Some(node) = stack.pop() { + while let Some(mut node) = stack.pop() { // REVIEW: A lot of labels appear here. // Perhaps I need to refactor something? + let mut node_label = self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))?; + if matches!( - self - .vertex_label(node.node())? - .ok_or_else(|| Error::NodeNoLabel(node.node()))? + node_label .label() .label(), GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt ) { - for parent in self.parents_of(node.node())? { - debug_assert!(matches!( - self.vertex_label(parent.node()), - Ok(Some(label)) if - label - .label() - .label() - .rule() - .is_some())); + // TODO: Try to update the end index of the + // node; if the node already has an ending + // index, clone the node, and update the + // ending index of the cloned node; otherwise, + // just set the ending index. + + if node_label.label().end().is_some() { + let cloned_node = + self.clone_node(node.node(), node.edge() + 1, false)?; + + self.transform_label(cloned_node, |mut label| { + label.set_end(pos + 1); + label + })?; + + node_label = self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))?; + } else { + self.transform_label(node.node(), |mut label| { + label.set_end(pos + 1); + label + })?; + } + + if node_label.clone_index().is_some() { + let mut parent_iter = self.parents_of(node.node())?; + + #[cfg(debug_assertions)] + assert_eq!(parent_iter.len(), 1); + + node = parent_iter.next().unwrap(); + + #[cfg(debug_assertions)] + assert!(self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))? + .is_packed()); + } + + let parents_iter = self.parents_of(node.node())?; + + let to_update = parents_iter + .clone() + .map(|parent| parent.node()) + .collect::<Vec<_>>(); + + for parent in parents_iter { + let parent_label = self + .vertex_label(parent.node())? + .ok_or_else(|| Error::NodeNoLabel(parent.node()))? + .label(); + + if parent_label.label().rule().is_none() { + crate::item::default::print_labels(atom, self.borrow()).unwrap(); + self.print_viz("dbg forest.gv").unwrap(); + + dbg!(parent, parent_label, label, node); + + panic!("assumption fails"); + } + + // debug_assert!(parent_label.label().rule().is_some()); + // debug_assert!(parent_label.end().is_none()); second_stack.extend(self.parents_of(parent.node())?.filter(|n| { matches!(self.vertex_label(n.node()), @@ -265,6 +328,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Some(TNT::Non(_)))) })); } + + for node in to_update { + self.transform_label(node, |mut label| { + label.set_end(pos + 1); + label + })?; + } } } @@ -293,7 +363,29 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { } for parent in stack.into_iter() { - if parent.edge() + 1 >= self.degree(parent.node())? { + let was_last_child = parent.edge() + 1 >= self.degree(parent.node())?; + + let overlap = { + if let Ok(child) = self.nth_child(parent.node(), parent.edge()) { + let edge_th_child = child; + let child_label = self + .vertex_label(edge_th_child)? + .ok_or(Error::NodeNoLabel(edge_th_child))?; + let child_start = child_label.label().start(); + let child_end = child_label.label().end(); + + child_start >= pos || matches!(child_end, Some(end) if end > pos) + } else { + // the root case + false + } + }; + + if overlap { + let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?; + + self.plant(cloned_node, fragment, non_empty)?; + } else if was_last_child { // dbg!(&fragment); self.plant(parent.node(), fragment, non_empty)?; } else { @@ -303,9 +395,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // do nothing continue; } - dbg!("clone?"); - let cloned_node = self.clone_node(nth_child)?; + // dbg!( + // label, + // atom_child, + // &parents, + // reduction_info, + // atom.query_reduction(label.label(), atom_child).unwrap() + // ); + + // self.print_viz("dbg forest.gv").unwrap(); + + let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?; self.plant(cloned_node, fragment, non_empty)?; } @@ -484,4 +585,22 @@ mod genins_test { Ok(()) } + + #[test] + fn test_reduction() -> Result<(), Box<dyn std::error::Error>> { + let grammar = new_paren_grammar()?; + + let atom = DefaultAtom::from_grammar(grammar)?; + + #[cfg(feature = "test-print-viz")] + atom.print_nfa("genins nfa.gv")?; + + // querying reductions + + println!("{:?}", atom.query_reduction(32, 17)?); + + // assert!(matches!(atom.query_reduction(35, 25), Ok(Some(&[2])))); + + Ok(()) + } } |