From 68d3baa1346aec734f4f98a3044c0056694f1b76 Mon Sep 17 00:00:00 2001 From: JSDurand 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 ++++++++++++++++++++++++++++++++++------ chain/src/item/default/splone.rs | 13 ++++++----- 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 Forest for DefaultForest> { let mut self_stack = Vec::with_capacity(fragment.nodes_len()); + use std::collections::HashSet; + + let mut frag_seen: HashSet = HashSet::with_capacity(fragment.nodes_len()); + let mut self_seen: HashSet = HashSet::with_capacity(fragment.nodes_len()); + let frag_root = if let Some(root) = fragment.root() { root } else { @@ -281,24 +286,46 @@ impl Forest for DefaultForest> { 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 Forest for DefaultForest> { 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 Forest for DefaultForest> { // 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. @@ -593,6 +594,12 @@ mod test_splone { let cloned = forest.clone_node(0, 0, false)?; + forest.plant( + cloned, + leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel), + true, + )?; + forest.plant( cloned, leaf!(GrammarLabel::new_closed(7, 1, 3), GrammarLabel), @@ -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)); -- cgit v1.2.3-18-g5258