diff options
Diffstat (limited to 'chain/src/item/default')
| -rw-r--r-- | chain/src/item/default/mod.rs | 122 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 37 |
2 files changed, 145 insertions, 14 deletions
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)] |