diff options
Diffstat (limited to 'chain/src/item/default/mod.rs')
-rw-r--r-- | chain/src/item/default/mod.rs | 122 |
1 files changed, 115 insertions, 7 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")?; |