From 81854107bcf0b4480cfb11e8af7fec6894240c0c Mon Sep 17 00:00:00 2001 From: JSDurand Date: Tue, 1 Aug 2023 11:47:44 +0800 Subject: Fix some bugs Some bugs are fixed: 1. If a non-terminal expansion can be reduced immediately, previously an extra node would be created that had no parents. Now this strange behaviour is corrected. 2. When performing reductions, a leaf non-terminal node would previously be regarded as completed. Now we will first try to complete that node, and then determine if the completion is successful, and finally determine the completedness according to the result. Of course some more tests are still pending, before I can confirm that no more bugs lurk around. --- chain/src/item/default/mod.rs | 122 ++++++++++++++++++++++++++++++++++++--- chain/src/item/default/splone.rs | 37 +++++++++--- 2 files changed, 145 insertions(+), 14 deletions(-) (limited to 'chain/src/item/default') 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 DefaultForest> { 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 DefaultForest { 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> { /// 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 { let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); let nodes_len = builder.nodes_len(); @@ -1200,7 +1244,7 @@ impl DefaultForest> { 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> { 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) } } @@ -1558,6 +1613,40 @@ mod item_test { Ok(()) } + #[test] + fn test_remove_prefix() -> Result<(), Box> { + 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> { 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> = 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> { 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> { /// /// 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> { 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> { 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> { 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> { 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)] -- cgit v1.2.3-18-g5258