From 9a317e56f8a6126583f7d0c431bf878d9b1fe7b1 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 8 Jul 2023 12:30:21 +0800 Subject: Finished the Emacs binding. Now the binding part is finished. What remains is a bug encountered when planting a fragment to the forest which intersects a packed node, which would lead to invalid forests. This will also cause problem when planting a packed fragment, but until now my testing grammars do not produce packed fragments, so this problem is not encountered yet. I am still figuring out efficient ways to solve this problem. --- chain/src/item/reduction.rs | 85 +++++++++++++++++++++++++++++++-------------- 1 file changed, 59 insertions(+), 26 deletions(-) (limited to 'chain/src/item/reduction.rs') diff --git a/chain/src/item/reduction.rs b/chain/src/item/reduction.rs index 89306e6..3c76c1e 100644 --- a/chain/src/item/reduction.rs +++ b/chain/src/item/reduction.rs @@ -122,6 +122,9 @@ impl DefaultForest> { /// The parameter `ter` is used to fill in segments for virtual /// nodes if they are found along the way. /// + /// The parameter `accept_root` controls whether we want to + /// perform reduction on the root. + /// /// # Errors /// /// 1. Index out of bounds: some node number is corrupted. @@ -132,12 +135,13 @@ impl DefaultForest> { pos: usize, ter: usize, atom: &DefaultAtom, + accept_root: bool, ) -> Result { let mut result = node; // step 1: Determine if this needs reductions. - if self.root() == Some(node) { + if !accept_root && self.root() == Some(node) { return Ok(result); } @@ -152,9 +156,30 @@ impl DefaultForest> { return Ok(result); } + // Data type for representing the status when performing a + // search. + + #[derive(PartialEq, Eq, Copy, Clone, Debug)] + enum Status { + Correct, + Incorrect, + Visited, + } + + impl From for Status { + fn from(value: bool) -> Self { + match value { + true => Self::Correct, + false => Self::Incorrect, + } + } + } + + use Status::*; + // step 2: Find descendents that need reductions. - let mut correct_ends: Map = Default::default(); + let mut correct_ends: Map = Default::default(); let mut order_of_correct_ends: Vec = Vec::new(); @@ -165,7 +190,7 @@ impl DefaultForest> { use std::{borrow::BorrowMut, io::Write}; // Whether or not to write a debug file. - let to_write = false; + let to_write = true; if to_write { if let Ok(ref mut file) = file.borrow_mut() { @@ -181,14 +206,18 @@ impl DefaultForest> { } } - if correct_ends.get(&top).is_some() { + let old_value = correct_ends.get(&top).copied(); + + if matches!(old_value, Some(Correct) | Some(Incorrect)) { continue 'stack_loop; } + correct_ends.insert(top, Visited); + let top_label = self.vertex_label(top)?.ok_or(Error::NodeNoLabel(top))?; if let Some(end) = top_label.label().end() { - correct_ends.insert(top, end == pos); + correct_ends.insert(top, (end == pos).into()); continue 'stack_loop; } @@ -216,8 +245,8 @@ impl DefaultForest> { 'child_loop: for child in self.children_of(top)? { match correct_ends.get(&child).copied() { - Some(true) => { - correct_ends.insert(top, true); + Some(Correct) => { + correct_ends.insert(top, Correct); inserted = true; } @@ -232,12 +261,15 @@ impl DefaultForest> { if has_unexplored_children { stack.push(top); - stack.extend(self.children_of(top)?); + stack.extend( + self.children_of(top)? + .filter(|child| correct_ends.get(child).is_none()), + ); } else if !inserted { - correct_ends.insert(top, false); + correct_ends.insert(top, Incorrect); } } else { - correct_ends.insert(top, false); + correct_ends.insert(top, Incorrect); } continue 'stack_loop; @@ -245,6 +277,7 @@ impl DefaultForest> { if top_label.is_packed() { let mut has_unexplored_children = false; + let mut inserted = false; if to_write { if let Ok(ref mut file) = file.borrow_mut() { @@ -255,12 +288,13 @@ impl DefaultForest> { for child in self.children_of(top)? { match correct_ends.get(&child).copied() { - Some(true) => { + Some(Correct) => { // NOTE: This is not recorded in the // correct orders, as we do not handle // packed nodes directly. - correct_ends.insert(top, true); + correct_ends.insert(top, Correct); + inserted = true; } None => { has_unexplored_children = true; @@ -280,9 +314,12 @@ impl DefaultForest> { if has_unexplored_children { stack.push(top); - stack.extend(self.children_of(top)?); - } else if correct_ends.get(&top).is_none() { - correct_ends.insert(top, false); + stack.extend( + self.children_of(top)? + .filter(|child| correct_ends.get(child).is_none()), + ); + } else if !inserted { + correct_ends.insert(top, Incorrect); } continue 'stack_loop; @@ -309,7 +346,7 @@ impl DefaultForest> { panic!("a terminal node {top} has no ending position?"); } Some(TNT::Non(nt)) => { - correct_ends.insert(top, true); + correct_ends.insert(top, Correct); self.close_pavi(atom.borrow(), PaVi::Virtual(nt, ter, top), pos)?; @@ -322,7 +359,7 @@ impl DefaultForest> { Some(end) => end, }; - correct_ends.insert(top, end == pos); + correct_ends.insert(top, (end == pos).into()); if end == pos { order_of_correct_ends.push(top); @@ -341,10 +378,12 @@ impl DefaultForest> { let last_child = self.nth_child(top, last_index)?; if let Some(child_correctness_value) = correct_ends.get(&last_child).copied() { - correct_ends.insert(top, child_correctness_value); + if child_correctness_value != Visited { + correct_ends.insert(top, child_correctness_value); - if child_correctness_value { - order_of_correct_ends.push(top); + if child_correctness_value == Correct { + order_of_correct_ends.push(top); + } } } else { stack.extend([top, last_child]); @@ -375,12 +414,6 @@ impl DefaultForest> { #[cfg(debug_assertions)] { - let label_label_label = label.label().label(); - - assert!(label_label_label.rule().is_none()); - - assert!(matches!(label_label_label.tnt(), Some(TNT::Non(_)))); - assert!(label.label().end().is_none()); assert_ne!(degree, 0); -- cgit v1.2.3-18-g5258