summaryrefslogtreecommitdiff
path: root/chain
diff options
context:
space:
mode:
Diffstat (limited to 'chain')
-rw-r--r--chain/src/default.rs21
-rw-r--r--chain/src/item/default/mod.rs50
-rw-r--r--chain/src/item/default/splone.rs113
-rw-r--r--chain/src/item/genins.rs11
4 files changed, 124 insertions, 71 deletions
diff --git a/chain/src/default.rs b/chain/src/default.rs
index 7de720f..23baa5f 100644
--- a/chain/src/default.rs
+++ b/chain/src/default.rs
@@ -20,10 +20,7 @@ use std::fmt::Display;
use graph_macro::Graph;
-use std::{
- borrow::Borrow,
- collections::{HashMap as Map, HashSet, TryReserveError},
-};
+use std::collections::{HashMap as Map, HashSet, TryReserveError};
/// The errors related to taking derivatives by chain rule.
#[non_exhaustive]
@@ -404,7 +401,7 @@ impl Chain for DefaultChain {
}
fn atom(&self) -> &Self::Atom {
- self.atom.borrow()
+ &self.atom
}
fn epsilon(&self) -> Result<bool, Self::Error> {
@@ -805,6 +802,8 @@ impl Chain for DefaultChain {
// The 1-th node is a dummy node that should be removed.
assert_ne!(root, 1);
+ // let _ = self.forest.print_viz("help.gv");
+
self.forest.remove_node(1)?;
let root_degree = self.forest.degree(root)?;
@@ -858,10 +857,7 @@ impl Chain for DefaultChain {
}
for clone in all_completed_clones {
- nodes.push(
- self.forest
- .reduction(clone, pos, ter, self.atom.borrow(), true)?,
- );
+ nodes.push(self.forest.reduction(clone, pos, ter, &self.atom, true)?);
}
} else if root_label.clone_index().is_some() {
panic!(
@@ -887,10 +883,7 @@ impl Chain for DefaultChain {
}
}
- nodes.push(
- self.forest
- .reduction(root, pos, ter, self.atom.borrow(), true)?,
- );
+ nodes.push(self.forest.reduction(root, pos, ter, &self.atom, true)?);
}
dbg!(&nodes);
@@ -1080,7 +1073,7 @@ mod test_chain {
for (pos, t) in input.iter().copied().enumerate().take(2) {
chain.chain(t, pos, no_item)?;
- chain.forest().print_viz(&format!("forest {pos}.gv"))?;
+ // chain.forest().print_viz(&format!("forest {pos}.gv"))?;
dbg!(pos, t);
}
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 7b0a843..0781dd2 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -498,7 +498,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
- let f_node_label_packed = builder_query(builder.borrow(), node_label.label());
+ let f_node_label_packed = builder_query(&builder, node_label.label());
if let Some((f_node, _f_label, f_packed)) = f_node_label_packed {
match (node_label.is_packed(), f_packed) {
@@ -512,8 +512,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.ok_or(Error::NodeNoLabel(child))?
.label();
- if let Some((f_child, _, _)) =
- builder_query(builder.borrow(), child_label)
+ if let Some((f_child, _, _)) = builder_query(&builder, child_label)
{
builder.add_edge(f_node, f_child, node_label)?;
} else {
@@ -524,12 +523,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
builder.add_edge(f_node, f_child, node_label)?;
}
}
- } else if !children_match_p(
- builder.borrow(),
- f_node,
- fragment.borrow(),
- node,
- )? {
+ } else if !children_match_p(&builder, f_node, fragment.borrow(), node)? {
let cloned = self.clone_node(f_node, 0, false)?;
let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
@@ -540,8 +534,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.ok_or(Error::NodeNoLabel(child))?
.label();
- if let Some((f_child, _, _)) =
- builder_query(builder.borrow(), child_label)
+ if let Some((f_child, _, _)) = builder_query(&builder, child_label)
{
builder.add_edge(cloned, f_child, node_label)?;
} else {
@@ -568,8 +561,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.vertex_label(child)?
.ok_or(Error::NodeNoLabel(child))?;
- let f_child =
- builder_query(builder.borrow(), child_label.label());
+ let f_child = builder_query(&builder, child_label.label());
if let Some((f_child, _, _)) = f_child {
builder.add_edge(cloned, f_child, child_label)?;
@@ -590,12 +582,8 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
for cloned_child in fragment.children_of(node)? {
let builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
- if !children_match_p(
- builder.borrow(),
- f_node,
- fragment.borrow(),
- cloned_child,
- )? {
+ if !children_match_p(&builder, f_node, fragment.borrow(), cloned_child)?
+ {
let cloned = self.clone_node(f_node, 0, false)?;
let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);
@@ -605,8 +593,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.vertex_label(child)?
.ok_or(Error::NodeNoLabel(child))?;
- let f_child =
- builder_query(builder.borrow(), child_label.label());
+ let f_child = builder_query(&builder, child_label.label());
if let Some((f_child, _, _)) = f_child {
builder.add_edge(cloned, f_child, child_label)?;
@@ -636,8 +623,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.vertex_label(child)?
.ok_or(Error::NodeNoLabel(child))?;
- let f_child =
- builder_query(builder.borrow(), child_label.label());
+ let f_child = builder_query(&builder, child_label.label());
if let Some((f_child, _, _)) = f_child {
builder.add_edge(f_node_clone, f_child, child_label)?;
@@ -654,12 +640,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
continue 'node_loop;
}
- if children_match_p(
- builder.borrow(),
- f_node_clone,
- fragment.borrow(),
- node,
- )? {
+ if children_match_p(&builder, f_node_clone, fragment.borrow(), node)? {
continue 'node_loop;
}
}
@@ -679,7 +660,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.vertex_label(child)?
.ok_or(Error::NodeNoLabel(child))?;
- let f_child = builder_query(builder.borrow(), child_label.label());
+ let f_child = builder_query(&builder, child_label.label());
if let Some((f_child, _, _)) = f_child {
builder.add_edge(cloned, f_child, child_label)?;
@@ -710,8 +691,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.vertex_label(child)?
.ok_or(Error::NodeNoLabel(child))?;
- let f_child =
- builder_query(builder.borrow(), child_label.label());
+ let f_child = builder_query(&builder, child_label.label());
if let Some((f_child, _, _)) = f_child {
builder.add_edge(f_node_clone, f_child, child_label)?;
@@ -729,7 +709,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
}
if children_match_p(
- builder.borrow(),
+ &builder,
f_node_clone,
fragment.borrow(),
cloned_child,
@@ -753,7 +733,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.vertex_label(child)?
.ok_or(Error::NodeNoLabel(child))?;
- let f_child = builder_query(builder.borrow(), child_label.label());
+ let f_child = builder_query(&builder, child_label.label());
if let Some((f_child, _, _)) = f_child {
builder.add_edge(cloned, f_child, child_label)?;
@@ -785,7 +765,7 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
.ok_or(Error::NodeNoLabel(child))?
.label();
- let f_child_label_packed = builder_query(builder.borrow(), child_label_label);
+ let f_child_label_packed = builder_query(&builder, child_label_label);
if let Some((f_child, _, _)) = f_child_label_packed {
builder.add_edge(f_node, f_child, node_label)?;
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index c9d9c5a..09fca0b 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -209,30 +209,17 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
}
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.is_none() {
- if node_degree == edge_index + 2 {
- let last_child = self.nth_child(node, node_degree - 1)?;
-
- if self.is_prefix(last_child, fragment.borrow())? {
- return Ok(node);
- }
- }
-
- if node_degree <= edge_index + 1 {
- self.plant(node, fragment, planted)?;
+ if let Some(node_to_plant) = self.find_node_to_plant(fragment, node, edge_index)? {
+ self.plant(node_to_plant, fragment, planted)?;
+ return Ok(node_to_plant);
+ } else {
return Ok(node);
}
-
- let cloned = self.clone_node(node, edge_index + 1, false)?;
-
- self.plant(cloned, fragment, planted)?;
-
- return Ok(cloned);
}
let new_label = self.create_new_label(node, None, edge_index, Some((fragment, planted)))?;
@@ -516,11 +503,11 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
if let Some((fragment, _planted)) = fragment {
let modified_degree = std::cmp::max(child_degree, 1) - 1;
- dbg!(node, end, edge_index, modified_degree);
+ // dbg!(node, end, edge_index, modified_degree);
- dbg!(child, child_degree);
+ // dbg!(child, child_degree);
- dbg!(&fragment);
+ // dbg!(&fragment);
if self.has_same_children(child, node, modified_degree, edge_index + 1)?
&& child_degree != 0
@@ -588,6 +575,92 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
}
}
+ /// Determine if the `fragment` should be planted anew. If so, return
+ /// a node to plant.
+ ///
+ /// Precisely speaking, if `node` has the fragment planted at the
+ /// position `edge_index` + 1, then there is no need to plant. If
+ /// not, but if `edge_index` + 1 is equal to the degree of `node`,
+ /// then we can directly plant under `node`.
+ ///
+ /// Moreover, if `node` is cloned, then do the same check for each of
+ /// its clones.
+ ///
+ /// # Assumption
+ ///
+ /// This function assumes the node is open-ended.
+ fn find_node_to_plant(
+ &mut self,
+ fragment: &DefaultForest<ForestLabel<GrammarLabel>>,
+ node: usize,
+ edge_index: usize,
+ ) -> Result<Option<usize>, Error> {
+ let mut node = node;
+
+ let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;
+
+ if node_label.is_packed() {
+ dbg!("split pack: {node}");
+
+ return Err(Error::SplitPack(node));
+ }
+
+ if node_label.clone_index().is_some() {
+ let mut parents = self.parents_of(node)?;
+
+ #[cfg(debug_assertions)]
+ assert_eq!(parents.len(), 1, "Assumption fails");
+
+ let packed = parents.next().unwrap().node();
+
+ for clone in self.children_of(packed)? {
+ let degree = self.degree(clone)?;
+
+ if degree == 0 {
+ return Ok(Some(clone));
+ }
+
+ if degree >= edge_index + 2 {
+ let index_child = self.nth_child(clone, edge_index + 1)?;
+
+ if self.is_prefix(index_child, fragment.borrow())? {
+ return Ok(None);
+ }
+ }
+
+ if degree == edge_index + 1 {
+ return Ok(Some(clone));
+ }
+ }
+
+ node = self.clone_node(node, edge_index + 1, false)?;
+
+ return Ok(Some(node));
+ }
+
+ let degree = self.degree(node)?;
+
+ if degree == 0 {
+ return Ok(Some(node));
+ }
+
+ if degree >= edge_index + 2 {
+ let index_child = self.nth_child(node, edge_index + 1)?;
+
+ if self.is_prefix(index_child, fragment.borrow())? {
+ return Ok(None);
+ }
+ }
+
+ if degree == edge_index + 1 {
+ return Ok(Some(node));
+ }
+
+ node = self.clone_node(node, edge_index + 1, false)?;
+
+ Ok(Some(node))
+ }
+
/// Compare if two nodes have the same children in the same order.
fn has_same_children(
&self,
diff --git a/chain/src/item/genins.rs b/chain/src/item/genins.rs
index ce34df9..ac521cc 100644
--- a/chain/src/item/genins.rs
+++ b/chain/src/item/genins.rs
@@ -213,7 +213,7 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
// operation for debugging purposes.
let mut to_print = true;
- if std::fs::metadata(format!("output/")).is_err() {
+ if std::fs::metadata("output/").is_err() {
to_print = false;
}
@@ -578,8 +578,15 @@ impl DefaultForest<ForestLabel<GrammarLabel>> {
let mut result = None;
+ // dbg!(leaf_label, &fragment);
+
+ // crate::item::default::print_labels(atom, fragment).unwrap();
+
+ // dbg!(self.vertex_label(node)?);
+
for (index, child) in self.children_of(node)?.enumerate() {
- if matches!(self.vertex_label(child)?, Some(child_label) if child_label == leaf_label)
+ // dbg!(self.vertex_label(child)?, child);
+ if matches!(self.vertex_label(child)?, Some(child_label) if child_label.label() == leaf_label.label())
{
result = Some((index, child));
break;
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-09-19 22:08:07 +0000