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.rs155
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(())
+ }
}