diff options
Diffstat (limited to 'chain')
| -rw-r--r-- | chain/src/default.rs | 126 | ||||
| -rw-r--r-- | chain/src/item/default/splone.rs | 100 | ||||
| -rw-r--r-- | chain/src/item/genins.rs | 184 | ||||
| -rw-r--r-- | chain/src/lib.rs | 98 |
4 files changed, 307 insertions, 201 deletions
diff --git a/chain/src/default.rs b/chain/src/default.rs index 31c1002..c873de7 100644 --- a/chain/src/default.rs +++ b/chain/src/default.rs @@ -110,13 +110,13 @@ impl Default for DerIterIndex { } /// A complex type used for storing values of edges with two layers. -type SecondTypeValue = (PaSe, bool, Vec<(Edge, usize)>); +type SecondTypeValue = (PaSe, bool, Vec<(Roi, usize)>); /// An iterator of TwoLayers. #[derive(Debug, Default)] pub struct DerIter { /// Stores edges of only one layer. - singles: Vec<(Edge, usize)>, + singles: Vec<(Roi, usize)>, /// Stores edges with two layers. They are grouped by their /// labels of the second layer. /// @@ -139,7 +139,7 @@ impl DerIter { label: usize, forest_source: PaSe, accepting: bool, - edges: Vec<(Edge, usize)>, + edges: Vec<(Roi, usize)>, ) { if let Some((_, _, vec)) = self.seconds.get_mut(&label) { vec.extend(edges); @@ -449,6 +449,30 @@ impl Chain for DefaultChain { self.current = new; } + fn update_epsilon( + &mut self, + node_id: usize, + edges: impl Iterator<Item = (Roi, usize)>, + ) -> Result<(), Self::Error> { + for (roi, _) in edges { + match roi.imaginary_part() { + Some(target) => { + if matches!(self.accepting_vec.get(target).copied(), Some(true)) { + let accepting_vec_len = self.accepting_vec.len(); + + *self + .accepting_vec + .get_mut(node_id) + .ok_or(Error::IndexOutOfBounds(node_id, accepting_vec_len))? = true; + } + } + None => {} + } + } + + Ok(()) + } + type DerIter = DerIter; fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error> { @@ -484,7 +508,7 @@ impl Chain for DefaultChain { child_iter: impl Iterator<Item = usize> + ExactSizeIterator + Clone, atom_child_iter: impl Iterator<Item = usize> + Clone, pase: PaSe, - mut output: impl AsMut<Vec<(Edge, usize)>>, + mut output: impl AsMut<Vec<(Roi, usize)>>, ) -> Result<(), Error> { // First check the values from iterators are all valid. let graph_len = chain.graph.nodes_len(); @@ -516,11 +540,9 @@ impl Chain for DefaultChain { for atom_child in atom_child_iter.clone() { let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap(); - let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap(); + // let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap(); - if !atom_child_empty_node { - num += child_iter.len(); - } + num += child_iter.len(); if atom_child_accepting { num += child_iter_total_degree; @@ -539,16 +561,19 @@ impl Chain for DefaultChain { let atom_child_accepting = chain.atom.is_accepting(atom_child).unwrap(); let atom_child_empty_node = chain.atom.is_empty_node(atom_child).unwrap(); - let edge = Edge::new(atom_child, pase, atom_child_accepting); + let roi = Edge::new(atom_child, pase, atom_child_accepting).into(); - if !atom_child_empty_node { - output.extend(child_iter.clone().map(|child| (edge, child))); - } + if atom_child_empty_node { + output.extend(child_iter.clone().map(|child| (child.into(), child))); + } else { + output.extend(child_iter.clone().map(|child| (roi, child))); + }; if atom_child_accepting { for child in child_iter.clone() { for (child_label, child_child) in chain.graph.labels_of(child).unwrap() { - output.extend(child_child.map(|target| (*child_label, target))); + output + .extend(child_child.map(|target| ((*child_label).into(), target))); } } } @@ -666,7 +691,8 @@ impl Chain for DefaultChain { if self.atom.is_empty_node(atom_child).unwrap() { der_iter.singles.extend(child_iter.clone().map(|child| { ( - Edge::new(virtual_node, virtual_pase, accepting), + Edge::new(virtual_node, virtual_pase, accepting) + .into(), child, ) })); @@ -684,7 +710,7 @@ impl Chain for DefaultChain { self.graph.labels_of(child).unwrap().flat_map( |(child_label, child_child_iter)| { child_child_iter.map(|child_child| { - (*child_label, child_child) + ((*child_label).into(), child_child) }) }, ) @@ -716,18 +742,39 @@ mod test_der_iter { let parent = Default::default(); - der_iter.singles.push((Edge::new(0, parent, true), 0)); + der_iter + .singles + .push((Edge::new(0, parent, true).into(), 0)); - der_iter.singles.push((Edge::new(1, parent, true), 0)); + der_iter + .singles + .push((Edge::new(1, parent, true).into(), 0)); - der_iter.singles.push((Edge::new(2, parent, true), 0)); + der_iter + .singles + .push((Edge::new(2, parent, true).into(), 0)); - der_iter.add_second_layer(3, parent, true, vec![(Edge::new(4, parent, true), 1)]); + der_iter.add_second_layer( + 3, + parent, + true, + vec![(Edge::new(4, parent, true).into(), 1)], + ); - der_iter.add_second_layer(6, parent, true, vec![(Edge::new(5, parent, true), 1)]); + der_iter.add_second_layer( + 6, + parent, + true, + vec![(Edge::new(5, parent, true).into(), 1)], + ); // add an entry with a repeated label - der_iter.add_second_layer(3, parent, true, vec![(Edge::new(7, parent, true), 2)]); + der_iter.add_second_layer( + 3, + parent, + true, + vec![(Edge::new(7, parent, true).into(), 2)], + ); assert_eq!( der_iter.next(), @@ -736,8 +783,8 @@ mod test_der_iter { parent, true, vec![ - (Edge::new(4, parent, true), 1), - (Edge::new(7, parent, true), 2) + (Edge::new(4, parent, true).into(), 1), + (Edge::new(7, parent, true).into(), 2) ] )) ); @@ -748,23 +795,23 @@ mod test_der_iter { 6, parent, true, - vec![(Edge::new(5, parent, true), 1)] + vec![(Edge::new(5, parent, true).into(), 1)] )) ); assert_eq!( der_iter.next(), - Some(TwoLayers::One(Edge::new(0, parent, true), 0)) + Some(TwoLayers::One(Edge::new(0, parent, true).into(), 0)) ); assert_eq!( der_iter.next(), - Some(TwoLayers::One(Edge::new(1, parent, true), 0)) + Some(TwoLayers::One(Edge::new(1, parent, true).into(), 0)) ); assert_eq!( der_iter.next(), - Some(TwoLayers::One(Edge::new(2, parent, true), 0)) + Some(TwoLayers::One(Edge::new(2, parent, true).into(), 0)) ); assert_eq!(der_iter.next(), None); @@ -800,6 +847,24 @@ mod test_chain { chain.chain(0, 11)?; chain.chain(0, 12)?; + let forest = &mut chain.forest; + + let node = forest + .query_label(ForestLabel::from(GrammarLabel::new(TNT::Non(6), 6))) + .unwrap(); + + forest.splone(node, Some(13), forest.degree(node)?)?; + + let node = forest + .query_label(ForestLabel::from(GrammarLabel::new(TNT::Non(1), 0))) + .unwrap(); + + forest.splone(node, Some(13), forest.degree(node)?)?; + + forest.splone(0, Some(13), forest.degree(0)?)?; + + forest.print_viz("forest.gv")?; + assert!(matches!(chain.epsilon(), Ok(true))); #[cfg(feature = "test-print-viz")] @@ -823,10 +888,13 @@ mod test_chain { chain.chain(0, 0)?; chain.chain(2, 1)?; chain.chain(2, 2)?; - // chain.chain(2, 3)?; - chain.chain(1, 3)?; + chain.chain(2, 3)?; + chain.chain(1, 4)?; + + chain.forest.print_viz("forest.gv")?; dbg!(chain.current(), chain.history()); + item::default::print_labels(&chain.atom, &chain.forest)?; #[cfg(feature = "test-print-viz")] { diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs index 4f4835b..851968c 100644 --- a/chain/src/item/default/splone.rs +++ b/chain/src/item/default/splone.rs @@ -19,6 +19,12 @@ fn get_rule_label(label: GrammarLabel) -> Option<usize> { } } +/// Existing or non-existing label. +enum Eon { + Ex(usize), + Nex(ForestLabel<GrammarLabel>), +} + impl DefaultForest<ForestLabel<GrammarLabel>> { /// Either "open split" or "closed split". /// @@ -56,6 +62,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node] /// for details. /// + /// # Return + /// + /// The function returns the new, splitted or cloned node, or the + /// old node, if nothing is performed. + /// /// # Name /// /// The name is a mixture of *split* and *clone*. @@ -74,12 +85,19 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// 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> { + pub(crate) fn splone( + &mut self, + node: usize, + end: Option<usize>, + edge_index: usize, + ) -> Result<usize, 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() { + self.print_viz("dbg forest.gv").unwrap(); + dbg!(self.vertex_label(node)?, end); return Err(Error::SplitPack(node)); } @@ -89,26 +107,26 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // 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(()); + if node_degree <= edge_index + 1 { + return Ok(node); } - dbg!(); - self.clone_node(node, edge_index + 1, false)?; + let cloned = self.clone_node(node, edge_index + 1, false)?; - return Ok(()); + return Ok(cloned); } let new_label = self.create_new_label(node, end, edge_index)?; - let new_label = if let Some(label) = new_label { - label - } else { - return Ok(()); + let new_label = match new_label { + Eon::Nex(label) => label, + Eon::Ex(existing) => { + return Ok(existing); + } }; if node_end.is_some() - || edge_index + 1 != node_degree + || edge_index + 1 < node_degree || node_label.clone_index().is_some() || new_label.clone_index().is_some() { @@ -168,7 +186,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // builder.add_edge(packed, node, new_label)?; // } - Ok(()) + Ok(node) } /// Procedure to split the node: @@ -180,12 +198,16 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { /// 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. + /// + /// # Return + /// + /// The function returns the new node index. fn split_node( &mut self, new_label: ForestLabel<GrammarLabel>, mut node: usize, edge_index: usize, - ) -> Result<(), Error> { + ) -> Result<usize, Error> { let end = new_label.label().end(); let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph); @@ -269,7 +291,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { }; for (parent, new_child) in parents { - if self.has_same_children_but_one( + if self.has_same_children_until( parent.node(), parent.node(), parent.edge(), @@ -284,18 +306,9 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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(()) + Ok(new_node) } /// Procedure for the new label: @@ -320,7 +333,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { node: usize, end: Option<usize>, edge_index: usize, - ) -> Result<Option<ForestLabel<GrammarLabel>>, Error> { + ) -> Result<Eon, Error> { let mut copied_label = self .vertex_label(node)? .ok_or(Error::NodeNoLabel(node))? @@ -337,7 +350,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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); + return Ok(Eon::Ex(child)); } } @@ -347,7 +360,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let clone_index = self.clone_node(first_child, 0, true)?; - Ok(Some(ForestLabel::new( + Ok(Eon::Nex(ForestLabel::new( copied_label, ForestLabelType::Cloned(clone_index), ))) @@ -356,17 +369,17 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { 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); + return Ok(Eon::Ex(existing)); } let clone_index = self.clone_node(existing, 0, true)?; - Ok(Some(ForestLabel::new( + Ok(Eon::Nex(ForestLabel::new( copied_label, ForestLabelType::Cloned(clone_index), ))) } else { - Ok(Some(plain_label)) + Ok(Eon::Nex(plain_label)) } } } @@ -396,9 +409,14 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { } /// 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( + /// another node, until a given index, where it points to another + /// given node. + /// + /// # Clones + /// + /// If `nodea` is a clone, it checks every clone to see if the + /// condition is satisfied for some clone. + fn has_same_children_until( &self, nodea: usize, nodeb: usize, @@ -408,14 +426,20 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let labela = self.vertex_label(nodea)?.ok_or(Error::NodeNoLabel(nodea))?; let children_b = self.children_of(nodeb)?; + if children_b.len() < edge_index + 1 { + return Err(Error::IndexOutOfBounds(edge_index, children_b.len() - 1)); + } + if labela.is_plain() { let children_a = self.children_of(nodea)?; - if children_a.len() != children_b.len() { + if children_a.len() < edge_index + 1 { return Ok(false); } - for (index, (childa, childb)) in children_a.zip(children_b).enumerate() { + for (index, (childa, childb)) in + children_a.zip(children_b).take(edge_index + 1).enumerate() + { if index != edge_index { if childa != childb { return Ok(false); @@ -437,11 +461,13 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { let children_a = self.children_of(branch)?; let children_b = children_b.clone(); - if children_a.len() != children_b.len() { + if children_a.len() < edge_index + 1 { continue 'branch_loop; } - for (index, (childa, childb)) in children_a.zip(children_b).enumerate() { + for (index, (childa, childb)) in + children_a.zip(children_b).take(edge_index + 1).enumerate() + { if index != edge_index { if childa != childb { continue 'branch_loop; diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs index 43807f8..4c51d9a 100644 --- a/chain/src/item/genins.rs +++ b/chain/src/item/genins.rs @@ -25,6 +25,12 @@ fn index_out_of_bounds_conversion(ge: GrammarError) -> Error { _ => Error::Invalid, } } + +/// Determine if a label is labelled by a terminal. +fn is_labelled_by_terminal(label: GrammarLabelType) -> bool { + matches!(label.tnt(), Some(t) if matches!(t, TNT::Ter(_))) +} + /// A helper function to generate a fragment of forest. /// /// It simply constructs a root node and then appends @@ -38,30 +44,43 @@ pub fn generate_fragment( labels: impl AsRef<[GrammarLabelType]>, pos: usize, ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, crate::default::Error> { - let mut labels_iter = labels.as_ref().iter(); - let mut result: DefaultForest<ForestLabel<GrammarLabel>>; - - if let Some(first_label) = labels_iter.next() { - result = DefaultForest::new_leaf(GrammarLabel::new(*first_label, pos)); - - let mut index = 0; - - for label in labels_iter { - result.plant( - index, - DefaultForest::new_leaf(GrammarLabel::new(*label, pos)), - false, - )?; - - // To prevent duplication of labels causing - // panics, we query the index of the new node. - index = result - .query_label(GrammarLabel::new(*label, pos).into()) - // REVIEW: Perhaps a LabelNoNode error? - .ok_or(Error::Invalid)?; - } + let labels_slice = labels.as_ref(); + + let labels_len = labels_slice.len(); + + let last_label = if labels_len > 0 { + labels_slice.get(labels_len - 1).copied().unwrap() } else { - result = Default::default(); + return Ok(Default::default()); + }; + + let labels_iter = labels_slice.iter(); + + let labels_iter_zipped = labels_iter + .clone() + .zip(labels_iter.skip(1).chain(std::iter::once(&last_label))); + + let mut mapped_iter = labels_iter_zipped.map(|(label, next_label)| { + if is_labelled_by_terminal(*next_label) { + GrammarLabel::new_closed(*label, pos, pos + 1) + } else { + GrammarLabel::new(*label, pos) + } + }); + + let first_label = mapped_iter.next().unwrap(); + + let mut result = DefaultForest::new_leaf(first_label); + + let mut index = 0; + + for label in mapped_iter { + result.plant(index, DefaultForest::new_leaf(label), false)?; + + index = result + .query_label(label.into()) + // REVIEW: Perhaps a LabelNoNode error? + .ok_or(Error::Invalid)?; } Ok(result) @@ -123,7 +142,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { &mut self, label: Edge, fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>, - atom_child_iter: impl Iterator<Item = usize>, + atom_child_iter: impl Iterator<Item = usize> + ExactSizeIterator, atom: &DefaultAtom, ) -> Result<PaSe, Error> { let fragment = fragment.borrow(); @@ -243,8 +262,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { // locate the nodes for reduction_nt in reduction_info.iter().copied().flatten().rev() { 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()))?; @@ -255,53 +272,32 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { .label(), GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt ) { - // 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 - })?; - } + let sploned_node = self.splone(node.node(), Some(pos), node.edge())?; + + node_label = self + .vertex_label(sploned_node)? + .ok_or(Error::NodeNoLabel(sploned_node))?; if node_label.clone_index().is_some() { - let mut parent_iter = self.parents_of(node.node())?; + let mut parent_iter = self.parents_of(sploned_node)?; #[cfg(debug_assertions)] - assert_eq!(parent_iter.len(), 1); + { + assert_eq!(parent_iter.len(), 1); - node = parent_iter.next().unwrap(); + assert!(self + .vertex_label(sploned_node)? + .ok_or(Error::NodeNoLabel(sploned_node))? + .is_packed()); + } - #[cfg(debug_assertions)] - assert!(self - .vertex_label(node.node())? - .ok_or_else(|| Error::NodeNoLabel(node.node()))? - .is_packed()); + node = parent_iter.next().unwrap(); + } else { + node = Parent::new(sploned_node, node.edge()); } 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())? @@ -312,14 +308,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { crate::item::default::print_labels(atom, self.borrow()).unwrap(); self.print_viz("dbg forest.gv").unwrap(); - dbg!(parent, parent_label, label, node); + dbg!(parent, parent_label, label, node, sploned_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()), Ok(Some(label)) @@ -328,13 +321,6 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { Some(TNT::Non(_)))) })); } - - for node in to_update { - self.transform_label(node, |mut label| { - label.set_end(pos + 1); - label - })?; - } } } @@ -357,59 +343,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> { self.print_viz("dbg forest.gv").unwrap(); #[cfg(test)] - genins_test::print_labels(atom, self).unwrap(); + genins_test::print_labels(atom, self.borrow()).unwrap(); return Err(Error::CannotPlant); } for parent in stack.into_iter() { - 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 - } - }; + let sploned_node = self.splone(parent.node(), None, parent.edge())?; - 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 { - let nth_child = self.nth_child(parent.node(), parent.edge() + 1)?; - - if self.is_prefix(nth_child, fragment)? { - // do nothing - continue; - } - - // 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)?; - } + self.plant(sploned_node, fragment, non_empty)?; non_empty = true; } diff --git a/chain/src/lib.rs b/chain/src/lib.rs index 745ad5a..a7740c2 100644 --- a/chain/src/lib.rs +++ b/chain/src/lib.rs @@ -64,12 +64,59 @@ 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. +/// A Real Or Imaginary edge. +/// +/// An imaginary edge will be ignored when adding edges. The +/// imaginary edges will be used to determine the acceptance of a +/// node, when and only when that new node turns out to have no +/// children. +/// +/// # Note +/// +/// Non, je ne suis pas un roi. Je ne sais pas qu'est-ce que vous +/// parlez. +#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)] +pub enum Roi { + /// A real edge is an ordinary edge. + Re(Edge), + /// The label of an imaginary edge is not important, so we only + /// record its target. + Im(usize), +} + +// Some convenient conversions + +impl From<Edge> for Roi { + fn from(edge: Edge) -> Self { + Self::Re(edge) + } +} + +impl From<usize> for Roi { + fn from(target: usize) -> Self { + Self::Im(target) + } +} + +impl Roi { + /// Return the real part if it is a real edge. + fn real_part(self) -> Option<Edge> { + if let Self::Re(edge) = self { + Some(edge) + } else { + None + } + } + + /// Return the imaginary part if it is an imaginary edge. + fn imaginary_part(self) -> Option<usize> { + if let Self::Im(target) = self { + Some(target) + } else { + None + } + } +} /// Each derivation is a concatenation of two items, so there are two /// layers. But some items have no children and are accepting, in @@ -81,7 +128,7 @@ impl core::fmt::Display for Edge { #[derive(Debug, Clone, Eq, PartialEq)] pub enum TwoLayers { /// One layer has no children. - One(Edge, usize), + One(Roi, usize), // REVIEW: Maybe we do not need to store an edge in the forest: we // only need the source of the edge? /// Both layers have children. @@ -90,7 +137,7 @@ pub enum TwoLayers { /// the source of the associated forest edge of the second layer, /// and the third is a list of edges, which are the common first /// layers. - Two(usize, PaSe, bool, Vec<(Edge, usize)>), + Two(usize, PaSe, bool, Vec<(Roi, usize)>), } /// The type of a collapsed iterator. @@ -122,7 +169,7 @@ where I: Iterator<Item = TwoLayers>, C: Chain<DerIter = I>, { - type Item = Result<(Edge, usize), <C as Chain>::Error>; + type Item = Result<(Roi, usize), <C as Chain>::Error>; fn next(&mut self) -> Option<Self::Item> { if self.stop { @@ -133,7 +180,11 @@ where match two_layer { TwoLayers::One(edge, to) => Some(Ok((edge, to))), TwoLayers::Two(label, forest_source, accepting, edges) => { - let new_index = match self.chain.extend(edges.into_iter()) { + let new_index = match self.chain.extend( + edges + .into_iter() + .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, target))), + ) { Ok(new) => new, Err(error) => { // Prevent further iterations. @@ -143,7 +194,10 @@ where } }; - Some(Ok((Edge::new(label, forest_source, accepting), new_index))) + Some(Ok(( + Edge::new(label, forest_source, accepting).into(), + new_index, + ))) } } } else { @@ -174,6 +228,14 @@ pub trait Chain: LabelExtGraph<Edge> { /// Update the history fn update_history(&mut self, new: usize); + /// Update the acceptance of a node, when and only when that node + /// turns out to have no children. + fn update_epsilon( + &mut self, + node_id: usize, + edges: impl Iterator<Item = (Roi, usize)>, + ) -> Result<(), Self::Error>; + /// An iterator that iterates all layers that need to be merged. type DerIter: Iterator<Item = TwoLayers>; @@ -181,10 +243,10 @@ pub trait Chain: LabelExtGraph<Edge> { fn derive(&mut self, t: usize, pos: usize) -> Result<Self::DerIter, Self::Error>; /// Take the union of all derivatives. - fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Edge, usize)>, Self::Error> { + fn union(&mut self, der_iter: Self::DerIter) -> Result<Vec<(Roi, usize)>, Self::Error> { // REVIEW: Find a way to avoid allocations. Collapsed::<_, Self>::collapse(der_iter, self) - .collect::<Result<Vec<(Edge, usize)>, Self::Error>>() + .collect::<Result<Vec<(Roi, usize)>, Self::Error>>() .map(|mut v| { v.retain(|(_, target)| { *target == 0 || matches!(self.degree(*target), Ok(deg) if deg != 0) @@ -200,7 +262,15 @@ pub trait Chain: LabelExtGraph<Edge> { let edges = self.union(der_iter)?; - let new_index = self.extend(edges)?; + let new_index = self.extend( + edges + .iter() + .filter_map(|(roi, target)| roi.real_part().map(|edge| (edge, *target))), + )?; + + if self.is_empty_node(new_index)? { + self.update_epsilon(new_index, edges.into_iter())?; + } self.update_history(new_index); |