diff options
| -rw-r--r-- | chain/src/atom/default.rs | 2 | ||||
| -rw-r--r-- | chain/src/default.rs | 11 | ||||
| -rw-r--r-- | chain/src/item/default/mod.rs | 122 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 37 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 23 | ||||
| -rw-r--r-- | chain/src/item/reduction.rs | 21 |
6 files changed, 186 insertions, 30 deletions
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs index e156178..6ae924f 100644 --- a/chain/src/atom/default.rs +++ b/chain/src/atom/default.rs @@ -123,7 +123,7 @@ impl DefaultAtom { .accepting_vec .iter() .enumerate() - .filter_map(|(index, pred)| (*pred).then(|| index)) + .filter_map(|(index, pred)| (*pred).then_some(index)) { print!("{nullable}, "); } diff --git a/chain/src/default.rs b/chain/src/default.rs index 5f83115..618e560 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -594,13 +594,10 @@ impl Chain for DefaultChain { && matches!(self.forest.degree(1), Ok(d) if d > 0) { // dbg!(self.forest.vertex_label(1)?, self.atom.empty()); - match self.forest.vertex_label(1) { - Ok(Some(label)) => { - if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) { - self.forest.remove_node(1)?; - } + if let Ok(Some(label)) = self.forest.vertex_label(1) { + if label.label().label().rule().map(|n| n << 1) == Some(self.atom.empty()) { + self.forest.remove_node(1)?; } - _ => {} } } @@ -1189,7 +1186,7 @@ mod test_chain { let no_item = false; - let input: &[usize] = &[3, 0, 2, 2, 2, 1, 1, 0, 1, 4, 2, 2, 1]; + let input: &[usize] = &[3, 0, 2, 1, 1, 0, 1, 4, 0, 2, 1]; let input_len = input.len(); diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs index b84d4ea..de43f37 100644 --- a/chain/src/item/default/mod.rs +++ b/chain/src/item/default/mod.rs @@ -965,7 +965,8 @@ impl<T: GraphLabel> DefaultForest<ForestLabel<T>> { return Ok(node); } - fragment.set_root(1)?; + // fragment.set_root(1)?; + fragment.remove_prefix(1)?; let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; @@ -1056,6 +1057,45 @@ impl<T: GraphLabel> DefaultForest<T> { Self { graph, root } } + /// Remove a prefix of the fragment. + /// + /// The new forest will have root set to 0, unless the entire + /// forest is removed. + pub fn remove_prefix(&mut self, prefix_len: usize) -> Result<(), Error> { + let nodes_len = self.nodes_len(); + + if prefix_len >= nodes_len { + self.graph = Default::default(); + self.root = None; + + return Ok(()); + } + + let mut new_graph = Default::default(); + let mut new_builder = PLGBuilderMut::from_graph_mut(&mut new_graph); + + let dummy_label = self.vertex_label(0)?.ok_or(Error::NodeNoLabel(0))?; + + for i in prefix_len..nodes_len { + let label = self.vertex_label(i)?.ok_or(Error::NodeNoLabel(i))?; + + new_builder.add_vertex(label); + } + + for (i, j) in self.edges() { + if i < prefix_len || j < prefix_len { + continue; + } + + new_builder.add_edge(i - prefix_len, j - prefix_len, dummy_label)?; + } + + self.graph = new_graph; + self.root = Some(0); + + Ok(()) + } + /// Set the root to the given node. pub fn set_root(&mut self, root: usize) -> Result<(), Error> { if root >= self.nodes_len() { @@ -1173,14 +1213,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// Set the position of every node. /// - /// If ALLP is non-nil or if the node is a terminal node, also set + /// If ALLP is `true` or if the node is a terminal node, also set /// the ending position whereever reasonable. + /// + /// If ALLP is `false` , always return `true`. Otherwise return + /// `true` if and only if the root is set to closed. If the + /// forest is empty, this returns `false`. pub(crate) fn set_pos( &mut self, atom: &DefaultAtom, pos: usize, allp: bool, - ) -> Result<(), Error> { + ) -> Result<bool, Error> { let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); let nodes_len = builder.nodes_len(); @@ -1200,7 +1244,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { builder.set_label(node, new_label)?; } - return Ok(()); + return Ok(true); } // We assign every node to be open first, and then start from @@ -1267,7 +1311,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { builder.set_label(node, new_label)?; } - Ok(()) + let root = if let Some(root) = self.root() { + root + } else { + return Ok(false); + }; + + let result = closed_nodes + .get(root) + .copied() + .ok_or(Error::IndexOutOfBounds(root, nodes_len))?; + + Ok(result) } } @@ -1559,6 +1614,40 @@ mod item_test { } #[test] + fn test_remove_prefix() -> Result<(), Box<dyn std::error::Error>> { + let mut forest = leaf!(0, usize); + + forest.plant(0, leaf!(1), false)?; + forest.plant(1, leaf!(2), false)?; + forest.plant(2, leaf!(3), false)?; + forest.plant(3, leaf!(4), false)?; + forest.plant(4, leaf!(5), false)?; + + forest.remove_prefix(2)?; + + dbg!(&forest); + + assert_eq!(forest.nodes_len(), 4); + assert_eq!(forest.root(), Some(0)); + + for i in 0..4 { + assert!(matches!(forest.vertex_label(i), + Ok(Some(label)) if + label == ForestLabel::new(i + 2, ForestLabelType::Plain))); + + for j in 0..4 { + if i + 1 == j { + assert!(matches!(forest.has_edge(i, j), Ok(true))); + } else { + assert!(matches!(forest.has_edge(i, j), Ok(false))); + } + } + } + + Ok(()) + } + + #[test] fn test_eq() -> Result<(), Box<dyn std::error::Error>> { let mut forest = leaf!(0, usize); @@ -1598,6 +1687,25 @@ mod item_test { atom.print_nullables(); + let non_nullable: usize = { + let mut result = 0usize; + + for i in 0..(atom.total()) { + if !atom.is_accepting(2 * i + 1)? { + result = i; + break; + } + } + + if result != 0 { + result + } else { + panic!("grammar has no non-nullable position?"); + } + }; + + println!("the chosen non-nullable is {non_nullable}"); + let mut forest: DefaultForest<ForestLabel<GrammarLabel>> = DefaultForest::new_leaf_raw( ForestLabel::new(GrammarLabel::new(TNT::Non(0), 0), ForestLabelType::Plain), ); @@ -1623,7 +1731,7 @@ mod item_test { forest.plant( 2, DefaultForest::new_leaf_raw(ForestLabel::new( - GrammarLabel::new(104, 0), + GrammarLabel::new(non_nullable, 0), ForestLabelType::Plain, )), false, @@ -1658,7 +1766,7 @@ mod item_test { // forest.print_viz("test.gv")?; - forest.set_pos(&atom, 1, true)?; + assert!(!forest.set_pos(&atom, 1, true)?); // forest.print_viz("test set.gv")?; diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs index 2ac3d73..9da156a 100644 --- a/chain/src/item/default/splone.rs +++ b/chain/src/item/default/splone.rs @@ -125,6 +125,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let new_label = self.create_new_label(node, end, edge_index, None)?; + // if node == 15 { + // dbg!(end, new_label, node_label); + // } + let new_label = match new_label { Eon::Nex(label) => label, Eon::Ex(existing) => { @@ -374,7 +378,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// /// 1. Copy the old label. /// - /// 2. Set the end to `pos`. + /// 2. Set the end to `end`. /// /// 3. Pack the label. /// @@ -412,9 +416,24 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { copied_label.set_end_option(end); - let label = ForestLabel::new(copied_label, ForestLabelType::Packed); + let packed_label = ForestLabel::new(copied_label, ForestLabelType::Packed); + let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain); + + let root = if let Some(root) = self.root() { + root + } else { + return Ok(Eon::Nex(plain_label)); + }; + + let packed_query = self.query_label(packed_label); + + // We ignore nodes without parents which are not roots. + if matches!(packed_query, Some(packed) if packed == root || + self.parents_of(packed)?.len() > 0) + { + // this is safe because of the 'if' guard + let packed = packed_query.unwrap(); - if let Some(packed) = self.query_label(label) { for child in self.children_of(packed)? { let child_degree = self.degree(child)?; @@ -457,9 +476,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Ok(Eon::Nex(cloned_label)) } else { - let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain); + let plain_query = self.query_label(plain_label); + + if matches!(plain_query, Some(plain) if plain == root || + self.parents_of(plain)?.len() > 0) + { + let existing = plain_query.unwrap(); - if let Some(existing) = self.query_label(plain_label) { let existing_degree = self.degree(existing)?; if self.has_same_children(existing, node, existing_degree, edge_index + 1)? { @@ -622,7 +645,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { for parent in parents { let mut parent_label = self .vertex_label(parent)? - .ok_or_else(|| Error::NodeNoLabel(parent))? + .ok_or(Error::NodeNoLabel(parent))? .label(); #[cfg(debug_assertions)] @@ -803,7 +826,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { for rule_parent in rule_parents { let mut rule_parent_label = self .vertex_label(rule_parent)? - .ok_or_else(|| Error::NodeNoLabel(rule_parent))? + .ok_or(Error::NodeNoLabel(rule_parent))? .label(); #[cfg(debug_assertions)] diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index bad0cfd..d5fb678 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -378,6 +378,8 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let reduced = self.reduction(nth_child, pos, ter, atom.borrow(), false)?; + // dbg!(reduced, nth_child, self.is_empty_node(reduced)?); + if reduced != nth_child && !self.is_empty_node(reduced)? { parents.clear(); parents.extend(self.parents_of(reduced)?); @@ -514,6 +516,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { if stack.is_empty() { dbg!( + is_empty_segment, label, atom_child, parents, @@ -698,12 +701,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Ok(nth_child) } } - PaVi::Virtual(nt, t, mut node) => { - let node_label_start = self + PaVi::Virtual(nt, t, node) => { + let node_label = self .vertex_label(node)? .ok_or(Error::NodeNoLabel(node))? - .label() - .start(); + .label(); + + let node_label_start = node_label.start(); let reduction_fragment = atom.generate_virtual_frags(nt, t, None); @@ -719,9 +723,16 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { for frag in reduction_fragment.into_iter().flatten() { let mut frag = frag.clone(); - frag.set_pos(atom, node_label_start, true)?; + let _root_closed_p = frag.set_pos(atom, node_label_start, true)?; + + // NOTE: If the root is closed, planting it might + // affect the original node, but we shall not deal + // with this phenomenon here. + // + // Instead, we will ignore the extra node at later + // stages. - node = self.plant_at_start(node, frag)?; + self.plant_at_start(node, frag)?; } Ok(node) diff --git a/chain/src/item/reduction.rs b/chain/src/item/reduction.rs index 3c76c1e..512862a 100644 --- a/chain/src/item/reduction.rs +++ b/chain/src/item/reduction.rs @@ -139,6 +139,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { ) -> Result<usize, Error> { let mut result = node; + // if node == 15 && pos == 2 { + // let _ = self.print_viz("pos really before splone.gv"); + // } + // step 1: Determine if this needs reductions. if !accept_root && self.root() == Some(node) { @@ -346,10 +350,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { panic!("a terminal node {top} has no ending position?"); } Some(TNT::Non(nt)) => { - correct_ends.insert(top, Correct); - self.close_pavi(atom.borrow(), PaVi::Virtual(nt, ter, top), pos)?; + // dbg!(top, nt, ter, pos, self.degree(top)?, degree); + + let correctness = self.degree(top)? > 0; + + correct_ends.insert(top, correctness.into()); + continue 'stack_loop; } None => { @@ -404,6 +412,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // NOTE: We must fix the order from top to bottom: this is the // reverse order of `order_of_correct_ends` . + // if node == 15 && pos == 2 { + // dbg!(&order_of_correct_ends); + // let _ = self.print_viz("pos before splone.gv"); + // } + for node in order_of_correct_ends.into_iter().rev() { let label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; let degree = self.degree(node)?; @@ -421,6 +434,10 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let last_index = degree - 1; + // if node == 15 && pos == 2 { + // let _ = self.print_viz("before splone.gv"); + // } + self.splone(node, Some(pos), last_index, false)?; } |