summaryrefslogtreecommitdiff
path: root/chain/src/item
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2023-02-12 15:49:28 +0800
committerJSDurand <mmemmew@gmail.com>2023-02-12 15:49:28 +0800
commit68d3baa1346aec734f4f98a3044c0056694f1b76 (patch)
treef5f7e114c6bdf848d7cdd77c319f1d379d82b847 /chain/src/item
parent987c84f3454c687cca0efe0d471fcf00e052ecab (diff)
fix clone not changing the root
Previously cloning a node does not alter the root of the forest, while it should alter the root if the cloned node was the root. This would affect how we compare the equalities of forests. It indeed resulted in anomalies that were hard to solve.
Diffstat (limited to 'chain/src/item')
-rw-r--r--chain/src/item/default/mod.rs47
-rw-r--r--chain/src/item/default/splone.rs13
2 files changed, 47 insertions, 13 deletions
diff --git a/chain/src/item/default/mod.rs b/chain/src/item/default/mod.rs
index 7ecc70d..1a00368 100644
--- a/chain/src/item/default/mod.rs
+++ b/chain/src/item/default/mod.rs
@@ -267,6 +267,11 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
let mut self_stack = Vec::with_capacity(fragment.nodes_len());
+ use std::collections::HashSet;
+
+ let mut frag_seen: HashSet<usize> = HashSet::with_capacity(fragment.nodes_len());
+ let mut self_seen: HashSet<usize> = HashSet::with_capacity(fragment.nodes_len());
+
let frag_root = if let Some(root) = fragment.root() {
root
} else {
@@ -281,24 +286,46 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
while let (Some(frag_top), Some(self_top)) =
(frag_stack.last().copied(), self_stack.last().copied())
{
+ frag_seen.insert(frag_top);
+ self_seen.insert(self_top);
+
frag_stack.pop();
self_stack.pop();
if fragment.vertex_label(frag_top)? != self.vertex_label(self_top)? {
// not a prefix
+ dbg!(
+ frag_top,
+ self_top,
+ fragment.vertex_label(frag_top)?,
+ self.vertex_label(self_top)?
+ );
return Ok(false);
}
- let mut self_children = self.children_of(self_top)?;
+ let self_children = self.children_of(self_top)?;
+ let frag_children = fragment.children_of(frag_top)?;
+
+ if frag_children.len() != self_children.len() {
+ dbg!(
+ frag_top,
+ self_top,
+ fragment.vertex_label(frag_top)?,
+ self.vertex_label(self_top)?
+ );
+ return Ok(false);
+ }
- for child in fragment.children_of(frag_top)? {
- if let Some(self_child) = self_children.next() {
- frag_stack.push(child);
- self_stack.push(self_child);
- } else {
- // too few children
+ for (frag_child, self_child) in frag_children.zip(self_children) {
+ if frag_seen.contains(&frag_child) && self_seen.contains(&self_child) {
+ continue;
+ } else if frag_seen.contains(&frag_child) || self_seen.contains(&self_child) {
+ dbg!();
return Ok(false);
}
+
+ frag_stack.push(frag_child);
+ self_stack.push(self_child);
}
}
@@ -425,6 +452,8 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
return Err(ForestLabelError::ClonePack.into());
}
+ let is_root_p = self.root() == Some(node_id);
+
// We are sure old_label is not packed here, so it is safe to
// unwrap.
let new_label = old_label
@@ -473,6 +502,10 @@ impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
// Make a new node
let new_index = builder.add_vertex(rep_label);
+ if is_root_p {
+ self.root = Some(new_index);
+ }
+
// Re-direct parents to the new node.
//
// This must be done before pointing the new node to the old
diff --git a/chain/src/item/default/splone.rs b/chain/src/item/default/splone.rs
index 1168539..4f4835b 100644
--- a/chain/src/item/default/splone.rs
+++ b/chain/src/item/default/splone.rs
@@ -1,3 +1,4 @@
+#![allow(dead_code)]
//! This module implements a function for "closing" and "splitting" a
//! node in a forest, and hence the name.
@@ -595,6 +596,12 @@ mod test_splone {
forest.plant(
cloned,
+ leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel),
+ true,
+ )?;
+
+ forest.plant(
+ cloned,
leaf!(GrammarLabel::new_closed(7, 1, 3), GrammarLabel),
false,
)?;
@@ -605,12 +612,6 @@ mod test_splone {
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));