diff options
Diffstat (limited to 'chain/src/item')
| -rw-r--r-- | chain/src/item/default/extract.rs | 509 | ||||
| -rw-r--r-- | chain/src/item/default/mod.rs | 62 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 10 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 18 | ||||
| -rw-r--r-- | chain/src/item/mod.rs | 15 | ||||
| -rw-r--r-- | chain/src/item/reduction.rs | 85 |
6 files changed, 609 insertions, 90 deletions
diff --git a/chain/src/item/default/extract.rs b/chain/src/item/default/extract.rs new file mode 100644 index 0000000..96f5119 --- /dev/null +++ b/chain/src/item/default/extract.rs @@ -0,0 +1,509 @@ +//! This module defines a function for extracting the "completed part" +//! of a forest. +//! +//! # Completed sub-forest +//! +//! The completed part of a forest refers to the sub-forest of the +//! forest that consists entirely of nodes whose ending positions are +//! set, and whose subtrees also consist of such nodes. +//! +//! # Definition +//! +//! To be more rigorous, we call a node *n* of a forest *F* complete +//! if its ending position is set. We call a sub-forest *S* of *F* +//! completed if the following two conditions are satisfied: +//! +//! 1. Every node in *S* is complete. +//! 2. For every node *n* in *S*, the subtree of *F* rooted at *n* +//! consists entirely of complete nodes. +//! +//! # Uniqueness of the maximal completed sub-forest +//! +//! **Lemma** +//! +//! For any forest *F*, there is only one maximal completed sub-forest +//! *S* of *F*. Here the maximality means that if *T* is a completed +//! sub-forest of *F* which contains *S*, then *S* is equal to *T*. +//! +//! Then by **the completed part** of a forest *F* we refer to the +//! unuique maximal completed sub-forest of *F*. +//! +//! **Proof** +//! +//! Note that if *S_1* and *S_2* are two completed sub-forests of *F*, +//! and if *S_1* is not contained in *S_2*, say *n* is a node in *S_1* +//! but not in *S_2*, then by adjoining the subtree of *S_2* rooted at +//! *n* to *S_1* we obtain a completed sub-forest *S_3* which contains +//! *S_1*, contradicting the maximality of *S_1*. Thus there can only +//! be one maximal completed sub-forest of a forest. +//! +//! # Connected component +//! +//! The extraction function actually returns the connected component +//! of the completed part of a forest which contains its root, as that +//! is what we care about the most. + +use super::*; + +impl DefaultForest<ForestLabel<GrammarLabel>> { + pub(crate) fn extract(&self, pos: usize) -> Result<Self, Error> { + // Preparations + + let nodes_len = self.nodes_len(); + + let mut graph = PLGraph::default(); + let mut builder = PLGBuilderMut::from_graph_mut(&mut graph); + let root = Some(0); + + // Now find the connected component of the completed part of + // `self` and clone that to graph by means of `builder`. + + // REVIEW: Maybe a small_vec can help here. + + // A fixed-size hash table, sort of. + let mut validity_array: Vec<bool> = std::iter::repeat(true).take(nodes_len).collect(); + + // Calculate the exact length to avoid too many allocations. + let mut stack_len = 0usize; + + // Use an iterator to avoid checking bounds in accessing + // elements of the array. + for (node, validity_ptr) in self.nodes().zip(validity_array.iter_mut()) { + if self + .vertex_label(node)? + .ok_or(Error::NodeNoLabel(node))? + .label() + .end() + .is_none() + { + *validity_ptr = false; + + stack_len += 1; + } + } + + dbg!(&validity_array); + + // A stack for propagating the falsehood to parents and + // children of incomplete nodes, like a plague. The only + // nodes that can stop the spread of this plague are packed + // nodes with a child that is not infected (yet) by the + // plague. + + let mut stack: Vec<usize> = Vec::with_capacity(stack_len); + + for (n, validity) in validity_array.iter().enumerate() { + if !*validity { + stack.push(n); + } + } + + while let Some(top) = stack.pop() { + 'parent_loop: for parent in self.parents_of(top)?.map(|p| p.node()) { + if !*validity_array + .get(parent) + .ok_or(Error::IndexOutOfBounds(parent, nodes_len))? + { + // already infected by the plague + + continue 'parent_loop; + } + + let should_spread_p = if self + .vertex_label(parent)? + .ok_or(Error::NodeNoLabel(parent))? + .is_packed() + { + !self + .children_of(parent)? + .any(|node| validity_array.get(node).copied() == Some(true)) + } else { + true + }; + + if should_spread_p { + *validity_array + .get_mut(parent) + .ok_or(Error::IndexOutOfBounds(parent, nodes_len))? = false; + stack.push(parent); + } + } + } + + let validity_array = validity_array; + + /// A little macro to produce a vector of valid children. + macro_rules! valid_children { + ($node:ident) => { + self.children_of($node)? + .filter(|child| validity_array.get(*child).copied() == Some(true)) + .collect::<Vec<usize>>() + }; + } + + dbg!(&validity_array); + + if validity_array.iter().all(|validity| !*validity) { + // every element is false + + let root = None; + + return Ok(Self { graph, root }); + } + + // Finally clone the connected component to the new graph. + + let root_label = GrammarLabel::new_closed(TNT::Non(0), 0, pos); + + let packed_label = ForestLabel::new(root_label, ForestLabelType::Packed); + + let plain_label = ForestLabel::new(root_label, ForestLabelType::Plain); + + let original_root_label; + + let original_root = if let Some(packed_node) = self.query_label(packed_label) { + original_root_label = packed_label; + + packed_node + } else if let Some(plain_node) = self.query_label(plain_label) { + original_root_label = plain_label; + + plain_node + } else { + let root = None; + return Ok(Self { graph, root }); + }; + + let mut roots_stack: Vec<usize>; + + if original_root_label.is_packed() { + roots_stack = valid_children!(original_root); + + match roots_stack.len() { + 0 => { + let root = None; + + return Ok(Self { graph, root }); + } + 1 => { + let child = *roots_stack.first().unwrap(); + + builder.add_vertex(self.vertex_label(child)?.ok_or(Error::NodeNoLabel(child))?); + } + _ => { + let builder_root = builder.add_vertex(original_root_label); + + for child in roots_stack.iter().copied() { + let child_node = builder.add_vertex( + self.vertex_label(child)?.ok_or(Error::NodeNoLabel(child))?, + ); + + builder.add_edge(builder_root, child_node, original_root_label)?; + } + } + } + } else { + builder.add_vertex(original_root_label); + + roots_stack = vec![original_root]; + } + + while let Some(top) = roots_stack.pop() { + let top_label = self.vertex_label(top)?.ok_or(Error::NodeNoLabel(top))?; + + let top_in_builder = match builder.query_label(top_label) { + Some(top_node) => top_node, + None => { + // an old cloned node now becomes a plain node + let plain_label = ForestLabel::new(top_label.label(), ForestLabelType::Plain); + + builder + .query_label(plain_label) + .unwrap_or_else(|| panic!("the top {top} should be planted already")) + } + }; + + 'children_loop: for child in self.children_of(top)? { + let child_label = self.vertex_label(child)?.ok_or(Error::NodeNoLabel(child))?; + + // filter out invalid children + if validity_array.get(child).copied() != Some(true) { + continue 'children_loop; + } + + // avoid unnecessary effort + if let Some(child_node) = builder.query_label(child_label) { + builder.add_edge(top_in_builder, child_node, child_label)?; + + continue 'children_loop; + } + + if child_label.is_packed() { + let child_valid_children = valid_children!(child); + + match child_valid_children.len() { + 0 => { + panic!("this case should not happen"); + } + 1 => { + // If a packed node only has one valid + // child, we clone a plain node instead. + + let child_child = *child_valid_children.first().unwrap(); + + let child_plain_label = + ForestLabel::new(child_label.label(), ForestLabelType::Plain); + + let child_plain_node = builder.add_vertex(child_plain_label); + + builder.add_edge( + top_in_builder, + child_plain_node, + child_plain_label, + )?; + + roots_stack.push(child_child); + } + _ => { + let child_node = builder.add_vertex(child_label); + + builder.add_edge(top_in_builder, child_node, child_label)?; + + roots_stack.push(child); + } + } + + continue 'children_loop; + } + + let child_node = builder.add_vertex(child_label); + + builder.add_edge(top_in_builder, child_node, child_label)?; + + roots_stack.push(child); + } + } + + Ok(Self { graph, root }) + } +} + +#[cfg(test)] +mod extract_tests { + use super::*; + + fn construct_test_forest( + ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> { + // node 0 + let mut result: DefaultForest<ForestLabel<GrammarLabel>> = DefaultForest::new_leaf( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Non(0)), 0, 3), + ); + + // node 1 + result.plant( + 0, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::Rule(15), 0, 3), + _ + ), + false, + )?; + + result.plant( + 1, + DefaultForest::new_leaf(GrammarLabel::new_closed( + GrammarLabelType::TNT(TNT::Non(0)), + 0, + 3, + )), + true, + )?; + + // node 2 + result.plant( + 0, + leaf!(GrammarLabel::new_closed(GrammarLabelType::Rule(6), 0, 1), _), + false, + )?; + + // node 3 + result.plant( + 2, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Ter(0)), 0, 1), + _ + ), + false, + )?; + + // node 4 + result.plant( + 0, + leaf!(GrammarLabel::new_closed(GrammarLabelType::Rule(7), 1, 3), _), + false, + )?; + + // node 5 + result.plant( + 4, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Non(0)), 1, 3), + _ + ), + false, + )?; + + // node 6 + result.plant( + 5, + leaf!(GrammarLabel::new_closed(GrammarLabelType::Rule(3), 1, 2), _), + false, + )?; + + // node 7 + result.plant( + 6, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Non(1)), 1, 2), + _ + ), + false, + )?; + + // node 8 + result.plant( + 7, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::Rule(11), 1, 2), + _ + ), + false, + )?; + + // node 9 + result.plant( + 8, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Ter(2)), 1, 2), + _ + ), + false, + )?; + + // Clone node 5 to have node 10 and node 11 + result.clone_node(5, 0, false)?; + + // node 12 + result.plant( + 11, + leaf!(GrammarLabel::new_closed(GrammarLabelType::Rule(3), 1, 3), _), + false, + )?; + + // node 13 + result.plant( + 12, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Non(1)), 1, 3), + _ + ), + false, + )?; + + result.plant( + 13, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::Rule(11), 1, 2), + _ + ), + true, + )?; + + // node 14 + result.plant( + 13, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::Rule(13), 2, 3), + _ + ), + false, + )?; + + // node 15 + result.plant( + 14, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Ter(2)), 2, 3), + _ + ), + false, + )?; + + // node 16 + result.plant( + 5, + leaf!(GrammarLabel::new(GrammarLabelType::Rule(4), 2), _), + false, + )?; + + // node 17 + result.plant( + 16, + leaf!(GrammarLabel::new(GrammarLabelType::TNT(TNT::Non(0)), 2), _), + false, + )?; + + // node 18 + result.plant( + 17, + leaf!(GrammarLabel::new_closed(GrammarLabelType::Rule(3), 2, 3), _), + false, + )?; + + // node 19 + result.plant( + 18, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Non(1)), 2, 3), + _ + ), + false, + )?; + + // node 20 + result.plant( + 19, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::Rule(11), 2, 3), + _ + ), + false, + )?; + + result.plant( + 20, + leaf!( + GrammarLabel::new_closed(GrammarLabelType::TNT(TNT::Ter(2)), 2, 3), + _ + ), + true, + )?; + + Ok(result) + } + + #[test] + fn test_extract() -> Result<(), Box<dyn std::error::Error>> { + let forest = construct_test_forest()?; + + assert_eq!(forest.nodes_len(), 21); + + forest.print_viz("forest before extraction.gv")?; + + let extract_result = forest.extract(3)?; + + extract_result.print_viz("extracted forest.gv")?; + + Ok(()) + } +} diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs index 47e8c90..28bdbee 100644 --- a/chain/src/item/default/mod.rs +++ b/chain/src/item/default/mod.rs @@ -12,7 +12,7 @@ use graph_macro::Graph; use std::collections::HashSet; -use core::fmt::Display; +use std::fmt::Display; /// The type of errors for forest operations. #[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)] @@ -216,6 +216,15 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { return Err(Error::IndexOutOfBounds(node_id, self.nodes_len())); } + // FIXME: We should take the presence of packed nodes into + // consideration. That is, the fragment might have already + // been planted and packed, and we need to account for such + // possibilities. + // + // Moreover, the fragments might also contain packed nodes, in + // which case we need to check these multiple possibilities + // are properly contained. + // We do a depth-first traversal to determine if every node // encountered has the same set of children (labels taken into // the consideration). @@ -450,7 +459,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { // Make sure it only has one parent, which is the // representative node. - assert_eq!(parents.len(), 1); + // assert_eq!(parents.len(), 1); // We checked its length is 1, so it is safe to unwrap // here. @@ -670,6 +679,8 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> { pub mod splone; +pub mod extract; + impl<T: GraphLabel> DefaultForest<T> { /// Create a forest with only one leaf from a raw label, unlike /// `new_leaf`, which transforms the label for convenience. @@ -798,53 +809,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Ok(()) } - /// Find the last child of the given node whose start and end - /// positions contain the given position. If no such child is - /// found, return `Ok(None)`. - /// - /// The returned tuple is of the form (child, index), where - /// `child` is the index of the child node in question, and - /// `index` means that the child is the `index`-th child of the - /// node. - #[allow(dead_code)] - pub(crate) fn position_search( - &self, - node: usize, - pos: usize, - ) -> Result<Option<(usize, usize)>, Error> { - fn range_contains(label: GrammarLabel, pos: usize) -> bool { - let start = label.start(); - - if let Some(end) = label.end() { - (start..end).contains(&pos) - } else { - (start..).contains(&pos) - } - } - - let node_label = self - .vertex_label(node)? - .ok_or(Error::NodeNoLabel(node))? - .label(); - - if !range_contains(node_label, pos) { - return Ok(None); - } - - for (index, child) in self.children_of(node)?.enumerate().rev() { - let child_label = self - .vertex_label(child)? - .ok_or(Error::NodeNoLabel(child))? - .label(); - - if range_contains(child_label, pos) { - return Ok(Some((child, index))); - } - } - - Ok(None) - } - /// Set the position of every node. /// /// If ALLP is non-nil or if the node is a terminal node, also set diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs index 581d1dc..da13c56 100644 --- a/chain/src/item/default/splone.rs +++ b/chain/src/item/default/splone.rs @@ -516,7 +516,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { if let Some((fragment, _planted)) = fragment { let modified_degree = std::cmp::max(child_degree, 1) - 1; - if self.has_same_children(child, node, modified_degree, edge_index)? + dbg!(node, end, edge_index, modified_degree); + + dbg!(child, child_degree); + + dbg!(&fragment); + + if self.has_same_children(child, node, modified_degree, edge_index + 1)? && child_degree != 0 { let last_child = self.nth_child(child, child_degree - 1)?; @@ -651,7 +657,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { } else if labela.clone_index().is_some() { let mut parentsa = self.parents_of(nodea)?; - assert_eq!(parentsa.len(), 1); + // assert_eq!(parentsa.len(), 1); let parenta = parentsa.next().unwrap().node(); diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 19f835b..e409c3c 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -32,7 +32,7 @@ pub(crate) fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { /// Determine if a label is labelled by a terminal. fn is_labelled_by_terminal(label: GrammarLabelType) -> bool { - matches!(label.tnt(), Some(t) if matches!(t, TNT::Ter(_))) + matches!(label.tnt(), Some(tnt) if matches!(tnt, TNT::Ter(_))) } /// A helper function to generate a fragment of forest. @@ -211,7 +211,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // Whether or not to print detailed graphs of each step of // operation for debugging purposes. - let to_print = false; + let to_print = true; let tnt_string = { let empty_p = atom_child_iter.len() == 0; @@ -376,7 +376,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { if let PaVi::Parent(node, edge, _) = pavi { let nth_child = self.nth_child(node, edge)?; - let reduced = self.reduction(nth_child, pos, ter, atom.borrow())?; + let reduced = self.reduction(nth_child, pos, ter, atom.borrow(), false)?; if reduced != nth_child && !self.is_empty_node(reduced)? { parents.clear(); @@ -700,10 +700,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let reduction_fragment = atom.generate_virtual_frags(nt, t, None); - // NOTE: the case of the root is exceptional - if reduction_fragment.is_none() && self.root() != Some(node) { - return Err(Error::CannotClose(nt, t, node, node_label_start)); - } + // Maybe we do not have to force the reduciton here? + + // // NOTE: the case of the root is exceptional + // if reduction_fragment.is_none() && self.root() != Some(node) { + // dbg!(self.root()); + // self.print_viz("cannot close.gv").unwrap(); + // return Err(Error::CannotClose(nt, t, node, node_label_start)); + // } for frag in reduction_fragment.into_iter().flatten() { let mut frag = frag.clone(); diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs index 54ca946..d2c3127 100644 --- a/chain/src/item/mod.rs +++ b/chain/src/item/mod.rs @@ -7,7 +7,7 @@ use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph}; -use core::borrow::Borrow; +use std::borrow::Borrow; /// A parent or a virtual segment. /// @@ -96,7 +96,7 @@ enum ForestLabelType { Cloned(usize), } -impl core::fmt::Display for ForestLabelType { +impl std::fmt::Display for ForestLabelType { fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { match self { Self::Packed => write!(f, "packed"), @@ -113,8 +113,8 @@ pub struct ForestLabel<T: GraphLabel> { status: ForestLabelType, } -impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> { - fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { +impl<T: GraphLabel> std::fmt::Display for ForestLabel<T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { if !matches!(self.status, ForestLabelType::Plain) { write!(f, "{}, {}", self.label, self.status) } else { @@ -132,8 +132,8 @@ pub enum ForestLabelError { ClonePack, } -impl core::fmt::Display for ForestLabelError { - fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { +impl std::fmt::Display for ForestLabelError { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { match self { Self::PackClone => write!(f, "cannot pack a cloned node"), Self::ClonePack => write!(f, "cannot clone a packed node"), @@ -230,6 +230,9 @@ impl<T: GraphLabel> From<T> for ForestLabel<T> { } } +// REVIEW: Should we move this trait (and only this trait) to a +// separate crate, or is it enough to keep it here? + /// The expected behaviours of an item derivation forest. /// /// Note that it requires only a subset of the functionalities of 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<ForestLabel<GrammarLabel>> { /// 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<ForestLabel<GrammarLabel>> { pos: usize, ter: usize, atom: &DefaultAtom, + accept_root: bool, ) -> Result<usize, Error> { 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<ForestLabel<GrammarLabel>> { 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<bool> 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<usize, bool> = Default::default(); + let mut correct_ends: Map<usize, Status> = Default::default(); let mut order_of_correct_ends: Vec<usize> = Vec::new(); @@ -165,7 +190,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { } } - 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<ForestLabel<GrammarLabel>> { '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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { 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<ForestLabel<GrammarLabel>> { #[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); |