summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-02-12 12:07:34 +0800
committerJSDurand <mmemmew@gmail.com>2023-02-12 12:07:34 +0800
commit987c84f3454c687cca0efe0d471fcf00e052ecab (patch)
tree04b9cf073a12adfb5d07ae308c3809e88cf4ebd2
parent265ff8f87dc7392fdf701f811eb2bf54d7bc6678 (diff)
Added the functionality of split or clone.
I need more than the ability to clone nodes: I also need to split the nodes. Now this seems to be correctly added.
-rw-r--r--chain/src/atom/default.rs31
-rw-r--r--chain/src/default.rs33
-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.rs760
-rw-r--r--chain/src/item/genins.rs155
-rw-r--r--chain/src/item/mod.rs56
-rw-r--r--chain/src/lib.rs19
-rw-r--r--chain/src/plan.org4
-rw-r--r--grammar/src/label.rs40
-rw-r--r--grammar/src/lib.rs9
-rw-r--r--graph/src/labelled/binary.rs4
-rw-r--r--nfa/src/lib.rs2
12 files changed, 1227 insertions, 62 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
diff --git a/grammar/src/label.rs b/grammar/src/label.rs
index 3f89d9a..058baaf 100644
--- a/grammar/src/label.rs
+++ b/grammar/src/label.rs
@@ -12,6 +12,15 @@ pub enum GrammarLabelType {
Rule(usize),
}
+impl Display for GrammarLabelType {
+ fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
+ match self {
+ Self::TNT(tnt) => write!(f, "{tnt}"),
+ Self::Rule(pos) => write!(f, "R({pos})"),
+ }
+ }
+}
+
// Some convenient conversions
impl From<usize> for GrammarLabelType {
@@ -71,11 +80,17 @@ pub struct GrammarLabel {
impl core::fmt::Display for GrammarLabel {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
- // Simply displaying this without the help of a grammar is not
- // of much help, so we just use the debug method to cheat,
- // haha.
-
- write!(f, "{:?}", self)
+ write!(
+ f,
+ "{}, {}, {}",
+ self.label,
+ self.start,
+ if let Some(end) = self.end {
+ format!("{end}")
+ } else {
+ "ε".to_owned()
+ }
+ )
}
}
@@ -89,6 +104,15 @@ impl GrammarLabel {
Self { label, start, end }
}
+ /// Construct a new label with an ending position.
+ #[inline]
+ pub fn new_closed(label: impl Into<GrammarLabelType>, start: usize, end: usize) -> Self {
+ let label = label.into();
+ let end = Some(end);
+
+ Self { label, start, end }
+ }
+
/// Return the end in the input.
#[inline]
pub fn end(&self) -> Option<usize> {
@@ -113,6 +137,12 @@ impl GrammarLabel {
self.end = Some(end);
}
+ /// Remove the ending boundary.
+ #[inline]
+ pub fn open_end(&mut self) {
+ self.end = None;
+ }
+
/// Return a string description with the help of the associated
/// grammar.
pub fn to_string(&self, grammar: &Grammar) -> Result<String, Error> {
diff --git a/grammar/src/lib.rs b/grammar/src/lib.rs
index a8e0fd7..ab0f693 100644
--- a/grammar/src/lib.rs
+++ b/grammar/src/lib.rs
@@ -538,6 +538,15 @@ impl Grammar {
Ok(self.reduction_map.get(&(pos1, pos2)).map(AsRef::as_ref))
}
+ /// Set the reduction information.
+ ///
+ /// This is used to set the reduction information for the virtual
+ /// nodes that are added after the left closure has been computed.
+ #[inline]
+ pub fn set_reduction(&mut self, pos1: usize, pos2: usize, info: Vec<usize>) {
+ self.reduction_map.insert((pos1, pos2), info);
+ }
+
// REVIEW: Do we have a better way to record expansion and
// reduction information than to compute the transitive closure?
diff --git a/graph/src/labelled/binary.rs b/graph/src/labelled/binary.rs
index 4ec7378..ce3a867 100644
--- a/graph/src/labelled/binary.rs
+++ b/graph/src/labelled/binary.rs
@@ -603,9 +603,11 @@ impl<'a, T: GraphLabel> BuilderMut for PLGBuilderMut<'a, T> {
// node_id is now guaranteed to be valid.
+ let old_label = self.graph.nodes.get(node_id).unwrap().label;
+
self.graph.nodes.get_mut(node_id).unwrap().label = label;
- self.graph.label_index_map.remove(&label);
+ self.graph.label_index_map.remove(&old_label);
self.graph.label_index_map.insert(label, node_id);
Ok(())
diff --git a/nfa/src/lib.rs b/nfa/src/lib.rs
index 4440ea6..07bbd5a 100644
--- a/nfa/src/lib.rs
+++ b/nfa/src/lib.rs
@@ -218,7 +218,6 @@ pub trait Nfa<T: GraphLabel>: LabelExtGraph<T> {
where
F: FnMut(T) -> bool,
{
- // self.closure(f, true, |two_edges| two_edges.second_edge().2)
unimplemented!("deprecated")
}
@@ -310,7 +309,6 @@ pub trait Nfa<T: GraphLabel>: LabelExtGraph<T> {
/// languages.
#[inline]
fn nulling(&mut self, _f: impl FnMut(T) -> bool) -> Result<(), Error> {
- // self.closure(f, false, |two_edges| two_edges.second_edge().2)
unimplemented!("deprecated")
}