summaryrefslogtreecommitdiff
path: root/chain/src/item/default
diff options
context:
space:
mode:
Diffstat (limited to 'chain/src/item/default')
-rw-r--r--chain/src/item/default/mod.rs50
-rw-r--r--chain/src/item/default/splone.rs113
2 files changed, 108 insertions, 55 deletions
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,
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-10 03:50:59 +0000