From 68d3baa1346aec734f4f98a3044c0056694f1b76 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Sun, 12 Feb 2023 15:49:28 +0800
Subject: 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.
---
 chain/src/item/default/mod.rs | 47 ++++++++++++++++++++++++++++++++++++-------
 1 file changed, 40 insertions(+), 7 deletions(-)

(limited to 'chain/src/item/default/mod.rs')

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
-- 
cgit v1.2.3-18-g5258