summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--chain/src/default.rs126
-rw-r--r--chain/src/item/default/splone.rs100
-rw-r--r--chain/src/item/genins.rs184
-rw-r--r--chain/src/lib.rs98
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);