diff options
Diffstat (limited to 'chain/src')
| -rw-r--r-- | chain/src/atom/default.rs | 31 | ||||
| -rw-r--r-- | chain/src/default.rs | 33 | ||||
| -rw-r--r-- | chain/src/item/default/mod.rs (renamed from chain/src/item/default.rs) | 176 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 760 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 155 | ||||
| -rw-r--r-- | chain/src/item/mod.rs | 56 | ||||
| -rw-r--r-- | chain/src/lib.rs | 19 | ||||
| -rw-r--r-- | chain/src/plan.org | 4 |
8 files changed, 1180 insertions, 54 deletions
diff --git a/chain/src/atom/default.rs b/chain/src/atom/default.rs index 9c91296..ec53596 100644 --- a/chain/src/atom/default.rs +++ b/chain/src/atom/default.rs @@ -415,7 +415,7 @@ impl DefaultAtom { .map(|(label, target_iter)| (*label, target_iter)) .collect(); - type TerminalsValue = (HashSet<(LabelType<TNT>, usize)>, bool); + type TerminalsValue = (HashSet<(LabelType<TNT>, usize, Option<Vec<usize>>)>, bool); let mut terminals_map: HashMap<usize, TerminalsValue> = HashMap::new(); @@ -454,14 +454,25 @@ impl DefaultAtom { // We checked this is safe above. let (set, _) = terminals_map.get_mut(&t).unwrap(); - set.extend(child_children_iter.map(|target| (*child_label, target))); + set.extend(child_children_iter.map(|target| { + ( + *child_label, + target, + grammar + .query_reduction(child, target) + .unwrap() + .map(|slice| slice.to_vec()), + ) + })); } } } } for (t, (set, accepting)) in terminals_map.into_iter() { - let new_index = nfa.extend(set).map_err(index_out_of_bounds_conversion)?; + let new_index = nfa + .extend(set.iter().map(|(label, target, _)| (*label, *target))) + .map_err(index_out_of_bounds_conversion)?; if accepting_vec.get(new_index).is_none() { #[cfg(debug_assertions)] @@ -473,6 +484,20 @@ impl DefaultAtom { let virtual_node = VirtualNode::new(nt, t); virtual_nodes.insert(virtual_node, new_index); + + // update the reduction information + for (_, target, info) in set.into_iter() { + if let Some(info) = info { + if !matches!( + grammar.query_reduction(new_index, target)?, + Some(original_reduction) + if original_reduction.len() + >= info.len()) + { + grammar.set_reduction(new_index, target, info); + } + } + } } } diff --git a/chain/src/default.rs b/chain/src/default.rs index 5e94623..31c1002 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -38,6 +38,8 @@ pub enum Error { CannotPlant, /// Trying to insert an empty item. EmptyItem, + /// Cannot split a packed node. + SplitPack(usize), /// An invalid situation happens. Invalid, } @@ -56,6 +58,7 @@ impl Display for Error { Self::CannotClone(fe) => write!(f, "cannot clone due to {fe}"), Self::CannotPlant => write!(f, "cannot plant a new forest fragment"), Self::EmptyItem => write!(f, "trying to insert an empty item"), + Self::SplitPack(n) => write!(f, "cannot split the packed node {n}"), Self::Invalid => write!(f, "invalid"), } } @@ -82,6 +85,7 @@ impl From<ForestError> for Error { ForestError::InvalidGraphError(ge) => ge.into(), ForestError::NodeNoLabel(n) => Error::NodeNoLabel(n), ForestError::LabelConversion(ce) => Error::CannotClone(ce), + ForestError::SplitPack(n) => Error::SplitPack(n), } } } @@ -783,7 +787,6 @@ mod test_chain { let mut chain = DefaultChain::unit(atom)?; chain.chain(3, 00)?; - dbg!("hi"); chain.chain(1, 01)?; chain.chain(2, 02)?; chain.chain(2, 03)?; @@ -811,6 +814,34 @@ mod test_chain { } #[test] + fn test_ambiguity() -> Result<(), Box<dyn std::error::Error>> { + let grammar = new_paren_grammar()?; + + let atom = DefaultAtom::from_grammar(grammar)?; + + let mut chain = DefaultChain::unit(atom)?; + chain.chain(0, 0)?; + chain.chain(2, 1)?; + chain.chain(2, 2)?; + // chain.chain(2, 3)?; + chain.chain(1, 3)?; + + dbg!(chain.current(), chain.history()); + + #[cfg(feature = "test-print-viz")] + { + chain.graph.print_viz("chain.gv")?; + chain.atom.print_nfa("nfa.gv")?; + chain.forest.print_viz("forest.gv")?; + item::default::print_labels(&chain.atom, &chain.forest)?; + } + + assert!(matches!(chain.epsilon(), Ok(true))); + + Ok(()) + } + + #[test] fn test_speed() -> Result<(), Box<dyn std::error::Error>> { let grammar = new_notes_grammar_no_regexp()?; diff --git a/chain/src/item/default.rs b/chain/src/item/default/mod.rs index f9d26ec..7ecc70d 100644 --- a/chain/src/item/default.rs +++ b/chain/src/item/default/mod.rs @@ -28,6 +28,8 @@ pub enum Error { InvalidGraphError(GError), /// Encounter an error when converting forest labels. LabelConversion(ForestLabelError), + /// Trying to split a packed node. + SplitPack(usize), } impl Display for Error { @@ -40,6 +42,7 @@ impl Display for Error { Error::InvalidGraphError(ge) => write!(f, "invalid error: {ge}"), Error::NodeNoLabel(n) => write!(f, "node {n} has no labels, but it should have one"), Error::LabelConversion(le) => write!(f, "fail to convert labels: {le}"), + Error::SplitPack(n) => write!(f, "cannot split the packed node {n}"), } } } @@ -226,6 +229,26 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { Self { graph, root } } + fn transform_label( + &mut self, + node_id: usize, + transform: impl FnOnce(T) -> T, + ) -> Result<(), Self::Error> { + let vertex_label = self + .vertex_label(node_id)? + .ok_or(Error::NodeNoLabel(node_id))?; + + let transformed_label = transform(vertex_label.label()); + + let transformed_label = ForestLabel::new(transformed_label, vertex_label.status); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + builder + .set_label(node_id, transformed_label) + .map_err(Into::into) + } + fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error> where F: Borrow<Self>, @@ -385,7 +408,12 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { Ok(()) } - fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error> { + fn clone_node( + &mut self, + node_id: usize, + preserved_edges_num: usize, + no_new_clone: bool, + ) -> Result<usize, Self::Error> { let builder = PLGBuilderMut::from_graph_mut(&mut self.graph); let old_label = builder @@ -393,20 +421,29 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { .ok_or(Error::NodeNoLabel(node_id))?; if old_label.is_packed() { + dbg!(node_id, old_label); return Err(ForestLabelError::ClonePack.into()); } // We are sure old_label is not packed here, so it is safe to // unwrap. - let new_label = old_label.clone(self).unwrap(); + let new_label = old_label + .clone::<DefaultForest<ForestLabel<T>>>(self.borrow()) + .unwrap(); if old_label.clone_index().is_some() { + if no_new_clone { + return Ok(new_label.clone_index().unwrap()); + } + let mut parents = self.parents_of(node_id)?; // Make sure it only has one parent, which is the // representative node. assert_eq!(parents.len(), 1); + // We checked its length is 1, so it is safe to unwrap + // here. let rep_node = parents.next().unwrap().node(); let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); @@ -415,8 +452,15 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { builder.add_edge(rep_node, new_clone, new_label)?; - // We checked its length is 1, so it is safe to unwrap - // here. + let preserve_children: Vec<_> = builder + .children_of(node_id)? + .take(preserved_edges_num) + .collect(); + + for child in preserve_children.into_iter() { + builder.add_edge(new_clone, child, new_label)?; + } + return Ok(new_clone); } @@ -455,7 +499,13 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { // new_label is cloned, so is guaranteed not to be packed, and // we are safe to unwrap. - let new_label = new_label.clone(self).unwrap(); + let new_label = new_label + .clone::<DefaultForest<ForestLabel<T>>>(self.borrow()) + .unwrap(); + + if no_new_clone { + return Ok(new_label.clone_index().unwrap()); + } let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); @@ -463,6 +513,15 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> { builder.add_edge(new_index, new_clone, new_label)?; + let preserve_children: Vec<_> = builder + .children_of(node_id)? + .take(preserved_edges_num) + .collect(); + + for child in preserve_children { + builder.add_edge(new_clone, child, new_label)?; + } + Ok(new_clone) } } @@ -490,8 +549,100 @@ impl<T: GraphLabel> PartialEq for DefaultForest<ForestLabel<T>> { } } +pub mod splone; + +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. + pub fn new_leaf_raw(label: T) -> Self { + let mut graph = PLGraph::default(); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut graph); + + let root = Some(builder.add_vertex(label)); + + Self { graph, root } + } +} + impl<T: GraphLabel> Eq for DefaultForest<ForestLabel<T>> {} +impl DefaultForest<ForestLabel<GrammarLabel>> { + /// Prints the forest without nodes that do not have ending + /// positions. + /// + /// Nodes without ending positions are "unclosed nodes" that only + /// serve the role of creating nodes with ending positions. + pub fn print_closed_viz(&self, filename: &str) -> Result<(), std::io::Error> { + let discard_nodes: std::collections::HashSet<_> = self + .nodes() + .filter(|node| match self.vertex_label(*node) { + Ok(label) => { + if let Some(label) = label { + label.label().end().is_none() + } else { + true + } + } + Err(_) => true, + }) + .collect(); + + let filename = format!("output/{filename}"); + + let preamble = "digraph nfa { + fontname=\"Helvetica,Arial,sans-serif\" + node [fontname=\"Helvetica,Arial,sans-serif\"] + edge [fontname=\"Helvetica,Arial,sans-serif\"] + rankdir=LR;\n"; + + let mut post = String::new(); + + for node in self.nodes() { + if discard_nodes.contains(&node) { + continue; + } + + post.push_str(&format!( + " {node} [label = \"{}\"]\n", + match self.vertex_label(node) { + Ok(Some(label)) => { + format!("{label}") + } + _ => { + " ε ".to_owned() + } + } + )); + } + + for (source, target) in self.edges() { + if discard_nodes.contains(&source) || discard_nodes.contains(&target) { + continue; + } + + post.push_str(&format!(" {source} -> {target}\n")); + } + + post.push_str("}\n"); + + let result = format!("{preamble}{post}"); + + if std::fs::metadata(&filename).is_ok() { + std::fs::remove_file(&filename)?; + } + + let mut file = std::fs::File::options() + .write(true) + .create(true) + .open(&filename)?; + + use std::io::Write; + + file.write_all(result.as_bytes()) + } +} + /// Print the labels found in the forest, so that we can easily /// understand what those labels mean. pub fn print_labels( @@ -609,11 +760,20 @@ mod item_test { // add a duplicate label forest.plant(3, leaf!(5), false)?; - let _len = forest.nodes_len(); + assert_eq!(forest.nodes_len(), 6); + + // add two children to 5 + + forest.plant(5, leaf!(6), false)?; + forest.plant(5, leaf!(7), false)?; + + // clone and preserve one child + let cloned = forest.clone_node(5, 1, false)?; - forest.clone_node(5)?; + assert_eq!(forest.nodes_len(), 10); - assert_eq!(forest.nodes_len(), 8); + assert_eq!(forest.degree(cloned)?, 1); + assert_eq!(forest.degree(5)?, 2); #[cfg(feature = "test-print-viz")] forest.print_viz("forest.gv")?; diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs new file mode 100644 index 0000000..1168539 --- /dev/null +++ b/chain/src/item/default/splone.rs @@ -0,0 +1,760 @@ +//! This module implements a function for "closing" and "splitting" a +//! node in a forest, and hence the name. + +use super::*; +use grammar::TNT; + +fn get_nt_label(label: GrammarLabel) -> Option<usize> { + match label.label() { + GrammarLabelType::TNT(TNT::Non(nt)) => Some(nt), + _ => None, + } +} + +fn get_rule_label(label: GrammarLabel) -> Option<usize> { + match label.label() { + GrammarLabelType::Rule(rule) => Some(rule), + _ => None, + } +} + +impl DefaultForest<ForestLabel<GrammarLabel>> { + /// Either "open split" or "closed split". + /// + /// An open split is an attempt to set the end of the node to + /// `None`, and a closed split is an attempt to set the end to a + /// specific position. + /// + /// Also this function preserves `edge_index + 1` many children + /// when splitting or cloning. + /// + /// To be more precise, this function performs the following + /// actions: + /// + /// 1. Make sure it is labelled by a nonterminal. + /// + /// 2. Check the status of the node. If it is packed, return an + /// error. + /// + /// 3. Make a new label according to the given `end`. See the + /// function + /// [`create_new_label`][DefaultForest::<ForestLabel<GrammarLabel>>::create_new_label] + /// for the process of making new labels. + /// + /// 4. If the new label is equal to the old label, and if + /// `edge_index + 1` is equal to the degree of the node, then do + /// nothing. + /// + /// 5. If the new label is equal to the old label but + /// `edge_index+1` is not equal to the degree of the node, then + /// clone the node while preserving `edge_index + 1` many + /// children. + /// + /// 6. If the new label is not equal to the old label, then split + /// the node. See the function + /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node] + /// for details. + /// + /// # Name + /// + /// The name is a mixture of *split* and *clone*. + /// + /// # NOTE + /// + /// We want to "do the same thing" to each parent of the node, + /// that should be checked to be labelled by a rule position. + /// + /// That is to say, if we replace the label of the node, we also + /// replace the label of the "rule parent". If we split the node, + /// the rule parents are also splitted in a parallel manner with + /// the splitted node. + /// + /// Also, when we refer to the parents of the node in the + /// descriptions of procedures below, we actually refer to the + /// parents of the rule parents, which should again be checked to + /// be labelled by non-terminals. + fn splone(&mut self, node: usize, end: Option<usize>, edge_index: usize) -> Result<(), Error> { + let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?; + + assert!(get_nt_label(node_label.label()).is_some()); + + if node_label.is_packed() { + return Err(Error::SplitPack(node)); + } + + let node_end = node_label.label().end(); + let node_degree = self.degree(node)?; + + // We can check the end to know whether the new label is equal + // to the old label. + if node_end == end { + if node_degree == edge_index + 1 { + return Ok(()); + } + + dbg!(); + self.clone_node(node, edge_index + 1, false)?; + + return Ok(()); + } + + let new_label = self.create_new_label(node, end, edge_index)?; + + let new_label = if let Some(label) = new_label { + label + } else { + return Ok(()); + }; + + if node_end.is_some() + || edge_index + 1 != node_degree + || node_label.clone_index().is_some() + || new_label.clone_index().is_some() + { + return self.split_node(new_label, node, edge_index); + } + + // replace the label directly + + // if new_label.clone_index().is_none() { + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + builder.set_label(node, new_label)?; + + let parents: Vec<_> = builder + .parents_of(node)? + .map(|parent| parent.node()) + .collect(); + + for parent in parents { + let mut parent_label = builder + .vertex_label(parent)? + .ok_or(Error::NodeNoLabel(parent))? + .label(); + + assert!(get_rule_label(parent_label).is_some()); + assert_eq!(builder.degree(parent)?, 1); + + if let Some(pos) = end { + parent_label.set_end(pos); + } else { + parent_label.open_end(); + } + + let parent_label = ForestLabel::from(parent_label); + + builder.set_label(parent, parent_label)?; + } + // } else { + // // REVIEW: Call `split_node` in this situation as well? + + // // If we are here, the new label should have a packed + // // parent. + // let packed = self + // .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed)) + // .unwrap(); + + // let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + // builder.set_label(node, new_label)?; + + // let parents: Vec<_> = builder.parents_of(node)?.collect(); + + // for parent in parents.iter() { + // builder.redirect(parent.node(), parent.edge(), packed)?; + // } + + // builder.add_edge(packed, node, new_label)?; + // } + + Ok(()) + } + + /// Procedure to split the node: + /// + /// 1. Create a new node with the new label. + /// + /// 2. Preserve the old children as specified by `edge_index + 1`. + /// + /// 3. For each parent, clone the parent. Replace the original + /// child of the parent, which pointed to the old node, by this + /// new node. Other children are inherited from the old parent. + fn split_node( + &mut self, + new_label: ForestLabel<GrammarLabel>, + mut node: usize, + edge_index: usize, + ) -> Result<(), Error> { + let end = new_label.label().end(); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + let mut new_node = builder.add_vertex(new_label); + + let new_packed = if new_label.clone_index().is_some() { + let packed = builder + .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed)) + .unwrap(); + + builder.add_edge(packed, new_node, new_label)?; + + Some(packed) + } else { + None + }; + + let preserve_children: Vec<_> = builder.children_of(node)?.take(edge_index + 1).collect(); + + for child in preserve_children { + builder.add_edge(new_node, child, new_label)?; + } + + let parents: Vec<_> = { + if let Some(label) = self.vertex_label(node)? { + if label.clone_index().is_some() { + let mut parents = self.parents_of(node)?; + assert_eq!(parents.len(), 1); + node = parents.next().unwrap().node(); + } + } + + let parents: Vec<_> = self.parents_of(node)?.collect(); + + let mut result: Vec<(Parent, usize)> = Vec::with_capacity( + parents + .iter() + .map(|parent| { + self.parents_of(parent.node()) + .map(|iter| iter.len()) + .unwrap_or(0) + }) + .sum(), + ); + + for parent in parents { + let mut parent_label = self + .vertex_label(parent.node())? + .ok_or_else(|| Error::NodeNoLabel(parent.node()))? + .label(); + + assert!(get_rule_label(parent_label).is_some()); + assert_eq!(self.degree(parent.node())?, 1); + + if let Some(pos) = end { + parent_label.set_end(pos); + } else { + parent_label.open_end(); + } + + let parent_label = ForestLabel::from(parent_label); + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + let new_parent = builder.add_vertex(parent_label); + + if let Some(packed) = new_packed { + new_node = packed; + } + + builder.add_edge(new_parent, new_node, new_label)?; + + result.extend( + self.parents_of(parent.node())? + .map(|parent_parent| (parent_parent, new_parent)), + ); + } + + result + }; + + for (parent, new_child) in parents { + if self.has_same_children_but_one( + parent.node(), + parent.node(), + parent.edge(), + new_child, + )? { + continue; + } + + // we don't add a child to parent.edge() here. + let cloned = self.clone_node(parent.node(), parent.edge(), false)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); + + builder.add_edge(cloned, new_child, new_label)?; + + let children_to_add: Vec<_> = builder + .children_of(parent.node())? + .skip(parent.edge() + 1) + .collect(); + + for child in children_to_add { + builder.add_edge(cloned, child, new_label)?; + } + } + + Ok(()) + } + + /// Procedure for the new label: + /// + /// 1. Copy the old label. + /// + /// 2. Set the end to `pos`. + /// + /// 3. Pack the label. + /// + /// 4. Check if this label already exists. If so, clone the label and + /// return it. + /// + /// 5. Else set the label to be a plain label. + /// + /// 6. Check if this plain label already exists. If so, clone the + /// existing label, and return the clone of the cloned label. + /// + /// 7. Else return the plain label. + fn create_new_label( + &mut self, + node: usize, + end: Option<usize>, + edge_index: usize, + ) -> Result<Option<ForestLabel<GrammarLabel>>, Error> { + let mut copied_label = self + .vertex_label(node)? + .ok_or(Error::NodeNoLabel(node))? + .label(); + + if let Some(pos) = end { + copied_label.set_end(pos); + } else { + copied_label.open_end(); + } + + let label = ForestLabel::new(copied_label, ForestLabelType::Packed); + + if let Some(packed) = self.query_label(label) { + for child in self.children_of(packed)? { + if self.has_same_children(child, node, self.degree(child)?, edge_index + 1)? { + return Ok(None); + } + } + + let mut packed_children = self.children_of(packed)?; + + let first_child = packed_children.next().unwrap(); + + let clone_index = self.clone_node(first_child, 0, true)?; + + Ok(Some(ForestLabel::new( + copied_label, + ForestLabelType::Cloned(clone_index), + ))) + } else { + let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain); + + if let Some(existing) = self.query_label(plain_label) { + if self.has_same_children(existing, node, self.degree(existing)?, edge_index + 1)? { + return Ok(None); + } + + let clone_index = self.clone_node(existing, 0, true)?; + + Ok(Some(ForestLabel::new( + copied_label, + ForestLabelType::Cloned(clone_index), + ))) + } else { + Ok(Some(plain_label)) + } + } + } + + /// Compare if two nodes have the same children in the same order. + fn has_same_children( + &self, + nodea: usize, + nodeb: usize, + edge_num_a: usize, + edge_num_b: usize, + ) -> Result<bool, Error> { + let children_a = self.children_of(nodea)?.take(edge_num_a); + let children_b = self.children_of(nodeb)?.take(edge_num_b); + + if children_a.len() != children_b.len() { + return Ok(false); + } + + for (childa, childb) in children_a.zip(children_b) { + if childa != childb { + return Ok(false); + } + } + + Ok(true) + } + + /// Detect if a node has a branch that has the same children as + /// another node, except at a given index, where it points to + /// another given node. + fn has_same_children_but_one( + &self, + nodea: usize, + nodeb: usize, + edge_index: usize, + alternative: usize, + ) -> Result<bool, Error> { + let labela = self.vertex_label(nodea)?.ok_or(Error::NodeNoLabel(nodea))?; + let children_b = self.children_of(nodeb)?; + + if labela.is_plain() { + let children_a = self.children_of(nodea)?; + + if children_a.len() != children_b.len() { + return Ok(false); + } + + for (index, (childa, childb)) in children_a.zip(children_b).enumerate() { + if index != edge_index { + if childa != childb { + return Ok(false); + } + } else if childa != alternative { + return Ok(false); + } + } + + Ok(true) + } else if labela.clone_index().is_some() { + let mut parentsa = self.parents_of(nodea)?; + + assert_eq!(parentsa.len(), 1); + + let parenta = parentsa.next().unwrap().node(); + + 'branch_loop: for branch in self.children_of(parenta)? { + let children_a = self.children_of(branch)?; + let children_b = children_b.clone(); + + if children_a.len() != children_b.len() { + continue 'branch_loop; + } + + for (index, (childa, childb)) in children_a.zip(children_b).enumerate() { + if index != edge_index { + if childa != childb { + continue 'branch_loop; + } + } else if childa != alternative { + continue 'branch_loop; + } + } + + return Ok(true); + } + + Ok(false) + } else { + // a packed node; this should not happen + unreachable!("should not examine children of a packed node") + } + } +} + +#[cfg(test)] +mod test_splone { + use super::*; + + use grammar::TNT::*; + + fn create_test_forest( + ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> { + let mut forest = leaf!(GrammarLabel::new(Non(0), 0), GrammarLabel); + + forest.plant( + 0, + leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel), + false, + )?; + forest.plant( + 1, + leaf!(GrammarLabel::new_closed(Ter(0), 0, 1), GrammarLabel), + false, + )?; + + forest.plant(0, leaf!(GrammarLabel::new(7, 1), GrammarLabel), false)?; + forest.plant(3, leaf!(GrammarLabel::new(Non(0), 1), GrammarLabel), false)?; + + forest.plant(4, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?; + forest.plant(5, leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel), false)?; + + forest.plant( + 6, + leaf!(GrammarLabel::new_closed(11, 1, 2), GrammarLabel), + false, + )?; + forest.plant( + 7, + leaf!(GrammarLabel::new_closed(Ter(2), 1, 2), GrammarLabel), + false, + )?; + + forest.plant( + 6, + leaf!(GrammarLabel::new_closed(13, 2, 3), GrammarLabel), + false, + )?; + forest.plant( + 9, + leaf!(GrammarLabel::new_closed(Ter(2), 2, 3), GrammarLabel), + false, + )?; + + forest.print_viz("test forest.gv")?; + + Ok(forest) + } + + fn splone_6_3_1() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> + { + let mut forest = create_test_forest()?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + builder.set_label( + 5, + ForestLabel::new(GrammarLabel::new_closed(3, 1, 3), ForestLabelType::Plain), + )?; + + builder.set_label( + 6, + ForestLabel::new( + GrammarLabel::new_closed(Non(1), 1, 3), + ForestLabelType::Plain, + ), + )?; + + Ok(forest) + } + + fn splone_6_2_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> + { + let mut forest = splone_6_3_1()?; + + let cloned = forest.clone_node(4, 0, false)?; + + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(3, 1, 2), GrammarLabel), + false, + )?; + + forest.plant( + cloned + 1, + leaf!(GrammarLabel::new_closed(Non(1), 1, 2), GrammarLabel), + false, + )?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + builder.add_edge(cloned + 2, 7, dummy_label)?; + + Ok(forest) + } + + fn splone_6_n_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> + { + let mut forest = splone_6_2_0()?; + + let cloned = forest.clone_node(4, 0, false)?; + + forest.plant(cloned, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?; + + forest.plant( + cloned + 1, + leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel), + false, + )?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + builder.add_edge(cloned + 2, 7, dummy_label)?; + + Ok(forest) + } + + fn splone_4_3_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> + { + let mut forest = splone_6_n_0()?; + + let cloned = forest.clone_node(0, 0, false)?; + + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(7, 1, 3), GrammarLabel), + false, + )?; + + forest.plant( + cloned + 1, + leaf!(GrammarLabel::new_closed(Non(0), 1, 3), GrammarLabel), + false, + )?; + + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel), + true, + )?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + builder.add_edge(cloned + 2, 5, dummy_label)?; + + Ok(forest) + } + + fn splone_17_3_0_15_3_0( + ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> { + let mut forest = splone_4_3_0()?; + + let to_clone = forest + .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(1), 1, 3))) + .unwrap(); + + let cloned = forest.clone_node(to_clone, 0, false)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0)); + + let child = builder + .query_label(ForestLabel::from(GrammarLabel::new_closed(11, 1, 2))) + .unwrap(); + + builder.add_edge(cloned, child, dummy_label)?; + + let to_clone = forest + .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(0), 1, 3))) + .unwrap(); + + let cloned = forest.clone_node(to_clone, 0, false)?; + + let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph); + + let child = builder + .query_label(ForestLabel::from(GrammarLabel::new(3, 1))) + .unwrap(); + + builder.add_edge(cloned, child, dummy_label)?; + + Ok(forest) + } + + #[test] + fn test() -> Result<(), Box<dyn std::error::Error>> { + let mut test_forest = create_test_forest()?; + + test_forest.splone(6, Some(3), 1)?; + + let answer = splone_6_3_1()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 3 1.gv")?; + panic!("splone(6, Some(3), 1) produced wrong forest"); + } + + test_forest.splone(6, Some(3), 1)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 3 1.gv")?; + panic!("repeated splone(6, Some(3), 1) produced wrong forest"); + } + + test_forest.splone(6, Some(2), 0)?; + + let answer = splone_6_2_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 2 0.gv")?; + panic!("splone(6, Some(2), 0) produced wrong forest"); + } + + test_forest.splone(6, Some(2), 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 2 0.gv")?; + panic!("repeated splone(6, Some(2), 0) produced wrong forest"); + } + + test_forest.splone(6, None, 0)?; + + let answer = splone_6_n_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 None 0.gv")?; + panic!("splone(6, None, 0) produced wrong forest"); + } + + test_forest.splone(14, None, 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 6 None 0.gv")?; + panic!("repeated splone(6, None, 0) produced wrong forest"); + } + + test_forest.splone(4, Some(3), 0)?; + + let answer = splone_4_3_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 4 3 0.gv")?; + panic!("splone(4, Some(3), 0) produced wrong forest"); + } + + test_forest.splone(4, Some(3), 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 4 3 0.gv")?; + panic!("repeated splone(4, Some(3), 0) produced wrong forest"); + } + + test_forest.splone(17, Some(3), 0)?; + test_forest.splone(15, Some(3), 0)?; + + let answer = splone_17_3_0_15_3_0()?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 17 3 0 15 3 0.gv")?; + panic!("splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest"); + } + + test_forest.splone(17, Some(3), 0)?; + test_forest.splone(15, Some(3), 0)?; + + if test_forest != answer { + test_forest.print_viz("sploned forest.gv")?; + answer.print_viz("splone 17 3 0 15 3 0.gv")?; + panic!( + "repeated splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest" + ); + } + + Ok(()) + } +} diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 9ed3b74..43807f8 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -68,7 +68,7 @@ pub fn generate_fragment( } /// Generate a virtual fragment representing the left-linear null -/// closure [nt]^t. +/// closure \[nt\]^t. pub fn virtual_generate_fragment( atom: impl Borrow<DefaultAtom>, nt: usize, @@ -130,12 +130,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let pase = label.forest_source(); - let _fragment_root = if let Some(root) = fragment.root() { + let fragment_root = if let Some(root) = fragment.root() { root } else { return Err(Error::EmptyItem); }; + let pos = fragment + .vertex_label(fragment_root)? + .ok_or(Error::NodeNoLabel(fragment_root))? + .label() + .start(); + // Ensure the last node in the PaSe is a terminal or a // non-terminal node, as an extra safety guard during // development. @@ -236,26 +242,83 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // locate the nodes for reduction_nt in reduction_info.iter().copied().flatten().rev() { - while let Some(node) = stack.pop() { + while let Some(mut node) = stack.pop() { // REVIEW: A lot of labels appear here. // Perhaps I need to refactor something? + let mut node_label = self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))?; + if matches!( - self - .vertex_label(node.node())? - .ok_or_else(|| Error::NodeNoLabel(node.node()))? + node_label .label() .label(), GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt ) { - for parent in self.parents_of(node.node())? { - debug_assert!(matches!( - self.vertex_label(parent.node()), - Ok(Some(label)) if - label - .label() - .label() - .rule() - .is_some())); + // TODO: Try to update the end index of the + // node; if the node already has an ending + // index, clone the node, and update the + // ending index of the cloned node; otherwise, + // just set the ending index. + + if node_label.label().end().is_some() { + let cloned_node = + self.clone_node(node.node(), node.edge() + 1, false)?; + + self.transform_label(cloned_node, |mut label| { + label.set_end(pos + 1); + label + })?; + + node_label = self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))?; + } else { + self.transform_label(node.node(), |mut label| { + label.set_end(pos + 1); + label + })?; + } + + if node_label.clone_index().is_some() { + let mut parent_iter = self.parents_of(node.node())?; + + #[cfg(debug_assertions)] + assert_eq!(parent_iter.len(), 1); + + node = parent_iter.next().unwrap(); + + #[cfg(debug_assertions)] + assert!(self + .vertex_label(node.node())? + .ok_or_else(|| Error::NodeNoLabel(node.node()))? + .is_packed()); + } + + let parents_iter = self.parents_of(node.node())?; + + let to_update = parents_iter + .clone() + .map(|parent| parent.node()) + .collect::<Vec<_>>(); + + for parent in parents_iter { + let parent_label = self + .vertex_label(parent.node())? + .ok_or_else(|| Error::NodeNoLabel(parent.node()))? + .label(); + + if parent_label.label().rule().is_none() { + crate::item::default::print_labels(atom, self.borrow()).unwrap(); + self.print_viz("dbg forest.gv").unwrap(); + + dbg!(parent, parent_label, label, node); + + panic!("assumption fails"); + } + + // debug_assert!(parent_label.label().rule().is_some()); + // debug_assert!(parent_label.end().is_none()); second_stack.extend(self.parents_of(parent.node())?.filter(|n| { matches!(self.vertex_label(n.node()), @@ -265,6 +328,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Some(TNT::Non(_)))) })); } + + for node in to_update { + self.transform_label(node, |mut label| { + label.set_end(pos + 1); + label + })?; + } } } @@ -293,7 +363,29 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { } for parent in stack.into_iter() { - if parent.edge() + 1 >= self.degree(parent.node())? { + let was_last_child = parent.edge() + 1 >= self.degree(parent.node())?; + + let overlap = { + if let Ok(child) = self.nth_child(parent.node(), parent.edge()) { + let edge_th_child = child; + let child_label = self + .vertex_label(edge_th_child)? + .ok_or(Error::NodeNoLabel(edge_th_child))?; + let child_start = child_label.label().start(); + let child_end = child_label.label().end(); + + child_start >= pos || matches!(child_end, Some(end) if end > pos) + } else { + // the root case + false + } + }; + + if overlap { + let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?; + + self.plant(cloned_node, fragment, non_empty)?; + } else if was_last_child { // dbg!(&fragment); self.plant(parent.node(), fragment, non_empty)?; } else { @@ -303,9 +395,18 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // do nothing continue; } - dbg!("clone?"); - let cloned_node = self.clone_node(nth_child)?; + // dbg!( + // label, + // atom_child, + // &parents, + // reduction_info, + // atom.query_reduction(label.label(), atom_child).unwrap() + // ); + + // self.print_viz("dbg forest.gv").unwrap(); + + let cloned_node = self.clone_node(parent.node(), parent.edge() + 1, false)?; self.plant(cloned_node, fragment, non_empty)?; } @@ -484,4 +585,22 @@ mod genins_test { Ok(()) } + + #[test] + fn test_reduction() -> Result<(), Box<dyn std::error::Error>> { + let grammar = new_paren_grammar()?; + + let atom = DefaultAtom::from_grammar(grammar)?; + + #[cfg(feature = "test-print-viz")] + atom.print_nfa("genins nfa.gv")?; + + // querying reductions + + println!("{:?}", atom.query_reduction(32, 17)?); + + // assert!(matches!(atom.query_reduction(35, 25), Ok(Some(&[2])))); + + Ok(()) + } } diff --git a/chain/src/item/mod.rs b/chain/src/item/mod.rs index c614802..284d640 100644 --- a/chain/src/item/mod.rs +++ b/chain/src/item/mod.rs @@ -5,16 +5,6 @@ //! More specifically, it implements the iten derivation forests for //! the machine. -// TODO: Implement an enumeration for Parent or Segment, perhaps -// called PaSe. - -// TODO: Move functions for handling forests, currently contained -// within the method derive to this module, and make them aware of the -// enumeration PaSe. - -// TODO: Implement the Item trait from semirings for the item -// derivation forest, and then we can easily execute items later on. - use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph}; use core::borrow::Borrow; @@ -88,7 +78,7 @@ impl core::fmt::Display for ForestLabelType { match self { Self::Packed => write!(f, "packed"), Self::Plain => write!(f, "plain"), - Self::Cloned(index) => write!(f, "the {index}-th clone"), + Self::Cloned(index) => write!(f, "clone({index})"), } } } @@ -102,7 +92,11 @@ pub struct ForestLabel<T: GraphLabel> { impl<T: GraphLabel> core::fmt::Display for ForestLabel<T> { fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { - writeln!(f, "label: {}, status: {}", self.label, self.status) + if !matches!(self.status, ForestLabelType::Plain) { + write!(f, "{}, {}", self.label, self.status) + } else { + write!(f, "{}", self.label) + } } } @@ -128,6 +122,10 @@ impl core::fmt::Display for ForestLabelError { impl std::error::Error for ForestLabelError {} impl<T: GraphLabel> ForestLabel<T> { + fn new(label: T, status: ForestLabelType) -> Self { + Self { label, status } + } + /// Retrieve the label. pub fn label(&self) -> T { self.label @@ -135,7 +133,7 @@ impl<T: GraphLabel> ForestLabel<T> { /// Return true if and only if this node is packed. pub fn is_packed(&self) -> bool { - matches!(self.status, ForestLabelType::Packed) + self.status == ForestLabelType::Packed } /// Retrieve the optional clone index. @@ -146,12 +144,18 @@ impl<T: GraphLabel> ForestLabel<T> { } } + /// Return true if and only if this node is a plain node. + pub fn is_plain(&self) -> bool { + self.status == ForestLabelType::Plain + } + /// Try to clone a node. pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError> where - F: Forest<T>, + F: LabelGraph<ForestLabel<T>>, { if self.is_packed() { + dbg!(); Err(ForestLabelError::ClonePack) } else { let clone_index = if let Some(old_index) = self.clone_index() { @@ -221,6 +225,13 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> { /// label. fn new_leaf(label: T) -> Self; + /// Transform the label at the given node. + fn transform_label( + &mut self, + node_id: usize, + transform: impl FnOnce(T) -> T, + ) -> Result<(), Self::Error>; + /// Detect if the fragment is a prefix of the sub-forest rooted at /// `node_id`. fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error> @@ -235,13 +246,22 @@ pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> { /// Clone a node by making a new node and making all the nodes /// that previously pointed to the old node now point to the new /// node, and the new node points to the old node. Return the - /// index of the new node. In addition, if the old node had - /// already been cloned, just return the index of its - /// representative. + /// index of the new node. However, if, and only if, + /// `no_new_clone` is `true`, do not make a new clone; instead + /// return the clone index that would be used if a new clone was + /// made. + /// + /// Also, `preserved_edges_num` many edges out of the old node + /// will be copied to be the children of the new node. /// /// The labels of the representing node and of the cloned node /// will be handled automatically. - fn clone_node(&mut self, node_id: usize) -> Result<usize, Self::Error>; + fn clone_node( + &mut self, + node_id: usize, + preserved_edges_num: usize, + no_new_clone: bool, + ) -> Result<usize, Self::Error>; } pub mod default; diff --git a/chain/src/lib.rs b/chain/src/lib.rs index 916678f..745ad5a 100644 --- a/chain/src/lib.rs +++ b/chain/src/lib.rs @@ -12,9 +12,6 @@ pub mod atom; pub mod item; -// TODO: We need a module for items, that serve the role of the -// forests now. - use graph::{error::Error as GError, LabelExtGraph}; use item::default::Error as ForestError; @@ -67,6 +64,13 @@ impl core::fmt::Display for Edge { } } +// TODO: Define an enumeration that stands for either an edge or a +// "phantom" edge. +// +// A phantom edge will be ignored when adding edges. The phantom +// edges will be used to determine the acceptance of a node, when and +// only when that new node turns out to have no children. + /// Each derivation is a concatenation of two items, so there are two /// layers. But some items have no children and are accepting, in /// which case we just skip that item completely, for performance @@ -179,7 +183,14 @@ pub trait Chain: LabelExtGraph<Edge> { /// Take the union of all derivatives. fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Edge, usize)>, Self::Error> { // REVIEW: Find a way to avoid allocations. - Collapsed::<_, Self>::collapse(der_iter, self).collect() + Collapsed::<_, Self>::collapse(der_iter, self) + .collect::<Result<Vec<(Edge, usize)>, Self::Error>>() + .map(|mut v| { + v.retain(|(_, target)| { + *target == 0 || matches!(self.degree(*target), Ok(deg) if deg != 0) + }); + v + }) } /// Use chain rule to compute the derivative with respect to a diff --git a/chain/src/plan.org b/chain/src/plan.org index 77d000c..02e14c9 100644 --- a/chain/src/plan.org +++ b/chain/src/plan.org @@ -86,14 +86,14 @@ + [ ] Implement the boolean semiring. + [ ] Implement the natural number semiring. + [ ] Implement the free semiring. -- [-] Implement languages. [4/6] +- [-] Implement languages. [5/6] + [X] First define a trait with the expected behaviours. + [X] Then implement them as doubly labelled graphs. + [X] Each edge in the chain-rule machine needs to be labelled also with a position in the forest. This perfectly solves the problem of those "plugs"! + [X] Then implement finding derivatives by use of the chain rule. - + [ ] Handle Semirings + + [X] Handle Semirings + [-] Tests - [X] Miscellaneous [1/1] + [X] Implement a function for NFA that checks if a given predicate |