path: root/chain/src/item/default/splone.rs

//! This module implements a function for "closing" and "splitting" a
//! node in a forest, and hence the name.

use super::*;
use grammar::TNT;

fn get_nt_label(label: GrammarLabel) -> Option<usize> {
    match label.label() {
        GrammarLabelType::TNT(TNT::Non(nt)) => Some(nt),
        _ => None,
    }
}

fn get_rule_label(label: GrammarLabel) -> Option<usize> {
    match label.label() {
        GrammarLabelType::Rule(rule) => Some(rule),
        _ => None,
    }
}

/// Existing or non-existing label.
#[derive(Debug, Copy, Clone)]
enum Eon {
    Ex(usize),
    Nex(ForestLabel<GrammarLabel>),
}

impl DefaultForest<ForestLabel<GrammarLabel>> {
    /// Either "open split" or "closed split".
    ///
    /// An open split is an attempt to set the end of the node to
    /// `None`, and a closed split is an attempt to set the end to a
    /// specific position.
    ///
    /// Also this function preserves `edge_index + 1` many children
    /// when splitting or cloning.
    ///
    /// To be more precise, this function performs the following
    /// actions:
    ///
    /// 1. Make sure it is labelled by a nonterminal.
    ///
    /// 2. Check the status of the node.  If it is packed, return an
    /// error.
    ///
    /// 3. Make a new label according to the given `end`.  See the
    /// function
    /// [`create_new_label`][DefaultForest::<ForestLabel<GrammarLabel>>::create_new_label]
    /// for the process of making new labels.
    ///
    /// 4. If the new label is equal to the old label, and if
    /// `edge_index + 1` is equal to the degree of the node, then do
    /// nothing.
    ///
    /// 5. If the new label is equal to the old label but
    /// `edge_index+1` is not equal to the degree of the node, then
    /// clone the node while preserving `edge_index + 1` many
    /// children.
    ///
    /// 6. If the new label is not equal to the old label, then split
    /// the node. See the function
    /// [`split_node`][DefaultForest::<ForestLabel<GrammarLabel>>::split_node]
    /// for details.
    ///
    /// # `completingp`
    ///
    /// When we are completing the forest at the end, we do not wish
    /// to keep the nodes at the end, so we pass a flag to inform the
    /// function of this intention.
    ///
    /// # Return
    ///
    /// The function returns the new, splitted or cloned node, or the
    /// old node, if nothing is performed.
    ///
    /// # Name
    ///
    /// The name is a mixture of *split* and *clone*.
    ///
    /// # NOTE
    ///
    /// We want to "do the same thing" to each parent of the node,
    /// that should be checked to be labelled by a rule position.
    ///
    /// That is to say, if we replace the label of the node, we also
    /// replace the label of the "rule parent".  If we split the node,
    /// the rule parents are also splitted in a parallel manner with
    /// the splitted node.
    ///
    /// Also, when we refer to the parents of the node in the
    /// descriptions of procedures below, we actually refer to the
    /// parents of the rule parents, which should again be checked to
    /// be labelled by non-terminals.
    pub(crate) fn splone(
        &mut self,
        node: usize,
        end: Option<usize>,
        edge_index: usize,
        completingp: bool,
    ) -> Result<usize, Error> {
        let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;

        assert!(get_nt_label(node_label.label()).is_some());

        if node_label.is_packed() {
            self.print_viz("dbg forest.gv").unwrap();
            dbg!(self.vertex_label(node)?, end);
            return Err(Error::SplitPack(node));
        }

        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 == end {
            if node_degree <= edge_index + 1 {
                return Ok(node);
            }

            let cloned = self.clone_node(node, edge_index + 1, false)?;

            return Ok(cloned);
        }

        let new_label = self.create_new_label(node, end, edge_index, None)?;

        let new_label = match new_label {
            Eon::Nex(label) => label,
            Eon::Ex(existing) => {
                return Ok(existing);
            }
        };

        if node_end.is_some()
            || edge_index + 1 < node_degree
            || node_label.clone_index().is_some()
            || new_label.clone_index().is_some()
        {
            return self.split_node(new_label, node, edge_index, completingp);
        }

        self.replace_label(node, new_label)?;

        Ok(node)
    }

    /// Split or clone, and then plant.
    ///
    /// # Splone
    ///
    /// This function is similar to
    /// [`splone`][DefaultForest::<ForestLabel<GrammarLabel>>::splone],
    /// but this is specialized for planting a fragment under the
    /// newly sploned node.  See the above-mentionned function for
    /// details on how to splone.
    ///
    /// # Parameter `planted`
    ///
    /// The function to plant a fragment takes a parameter `planted`,
    /// which indicates whether or not the fragment had already been
    /// planted before.  This is used to avoid re-inserting fragments
    /// into the forest.  One can just add an edge and be done.
    ///
    /// # Special treatment
    ///
    /// This function is aimed at solving a specific problem that the
    /// function
    /// [`splone`][DefaultForest::<ForestLabel<GrammarLabel>>::splone]
    /// faces: duplication of nodes after planting a fragment under
    /// the newly sploned node.  That is, if we splone a node and then
    /// immediately plant a fragment under it, then that new node will
    /// become a different node from the original sploned node, so if
    /// we splone another node that ends up creating the same sploned
    /// node, and if we plant the same fragment under it, we will end
    /// up creating duplicated cloned nodes, which later mess up the
    /// forests.
    ///
    /// So this function first checks if the would-be-sploned node
    /// with the fragment planted already exists; if so, then just
    /// return that node, otherwise we perform the usual sploning and
    /// plant the fragment after the splone.
    ///
    /// # Special values of two parameters to `splone`
    ///
    /// Since we want to plant a fragment under the splone, the
    /// parameter `end` to the splone function is set to `None`
    /// automatically.
    ///
    /// Moreover, the parameter `completingp` is for completing the
    /// forest at the end, while we are definitely not at the end if
    /// we are going to plant a fragment after sploning, so that
    /// parameter is automatically set to `false` as well.
    pub(crate) fn splant(
        &mut self,
        node: usize,
        edge_index: usize,
        fragment: &DefaultForest<ForestLabel<GrammarLabel>>,
        planted: bool,
    ) -> Result<usize, Error> {
        let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;

        assert!(get_nt_label(node_label.label()).is_some());

        if node_label.is_packed() {
            self.print_viz("dbg forest.gv").unwrap();
            dbg!(self.vertex_label(node)?);
            return Err(Error::SplitPack(node));
        }

        let node_end = node_label.label().end();

        // We can check the end to know whether the new label is equal
        // to the old label.
        if node_end.is_none() {
            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 new_label = self.create_new_label(node, None, edge_index, Some((fragment, planted)))?;

        let new_label = match new_label {
            Eon::Nex(label) => label,
            Eon::Ex(existing) => {
                return Ok(existing);
            }
        };

        let splitted = self.split_node(new_label, node, edge_index, false)?;

        self.plant(splitted, fragment, planted)?;

        Ok(splitted)
    }

    /// Replace the label of a node by a new label.
    ///
    /// This also handles the labels of parents of the node.
    fn replace_label(
        &mut self,
        node: usize,
        new_label: ForestLabel<GrammarLabel>,
    ) -> Result<(), Error> {
        let end = new_label.label().end();

        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

        builder.set_label(node, new_label)?;

        let parents: Vec<_> = builder
            .parents_of(node)?
            .map(|parent| parent.node())
            .collect();

        for parent in parents {
            let mut parent_label = builder
                .vertex_label(parent)?
                .ok_or(Error::NodeNoLabel(parent))?
                .label();

            if get_rule_label(parent_label).is_none() {
                self.print_viz("dbg forest.gv").unwrap();
                panic!("assumption fails");
            }

            assert_eq!(builder.degree(parent)?, 1);

            if let Some(pos) = end {
                parent_label.set_end(pos);
            } else {
                parent_label.open_end();
            }

            let parent_label = ForestLabel::from(parent_label);

            builder.set_label(parent, parent_label)?;
        }

        Ok(())
    }

    /// Procedure to split the node:
    ///
    /// 1. Create a new node with the new label.
    ///
    /// 2. Preserve the old children as specified by `edge_index + 1`.
    ///
    /// 3. For each parent, clone the parent.  Replace the original
    /// child of the parent, which pointed to the old node, by this
    /// new node.  Other children are inherited from the old parent.
    ///
    /// # Return
    ///
    /// The function returns the new node index.
    fn split_node(
        &mut self,
        new_label: ForestLabel<GrammarLabel>,
        mut node: usize,
        edge_index: usize,
        completingp: bool,
    ) -> Result<usize, Error> {
        let end = new_label.label().end();

        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

        let new_node = builder.add_vertex(new_label);

        let new_packed = if new_label.clone_index().is_some() {
            let packed = builder
                .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed))
                .unwrap();

            builder.add_edge(packed, new_node, new_label)?;

            Some(packed)
        } else {
            None
        };

        let preserve_children: Vec<_> = builder.children_of(node)?.take(edge_index + 1).collect();

        for child in preserve_children {
            builder.add_edge(new_node, child, new_label)?;
        }

        let parents: Vec<_> = {
            if let Some(label) = self.vertex_label(node)? {
                if label.clone_index().is_some() {
                    let mut parents = self.parents_of(node)?;
                    assert_eq!(parents.len(), 1);
                    node = parents.next().unwrap().node();
                }
            }

            let parents: Vec<_> = self.parents_of(node)?.collect();

            let mut result: Vec<(Parent, usize)> = Vec::with_capacity(
                parents
                    .iter()
                    .map(|parent| {
                        self.parents_of(parent.node())
                            .map(|iter| iter.len())
                            .unwrap_or(0)
                    })
                    .sum(),
            );

            for parent in parents {
                let mut parent_label = self
                    .vertex_label(parent.node())?
                    .ok_or_else(|| Error::NodeNoLabel(parent.node()))?
                    .label();

                assert!(get_rule_label(parent_label).is_some());

                if self.degree(parent.node())? != 1 {
                    dbg!(parent);
                    self.print_viz("dbg forest.gv").unwrap();

                    panic!("assumption fails");
                }

                if let Some(pos) = end {
                    parent_label.set_end(pos);
                } else {
                    parent_label.open_end();
                }

                let parent_label = ForestLabel::from(parent_label);

                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

                let new_parent = builder.add_vertex(parent_label);

                if let Some(packed) = new_packed {
                    builder.add_edge(new_parent, packed, new_label)?;
                } else {
                    builder.add_edge(new_parent, new_node, new_label)?;
                }

                result.extend(
                    self.parents_of(parent.node())?
                        .map(|parent_parent| (parent_parent, new_parent)),
                );
            }

            result
        };

        for (parent, new_child) in parents {
            if !completingp {
                if self.has_same_children_until(
                    parent.node(),
                    parent.node(),
                    parent.edge(),
                    new_child,
                )? {
                    continue;
                }

                // we don't add a child to parent.edge() here.
                let cloned = self.clone_node(parent.node(), parent.edge(), false)?;

                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

                builder.add_edge(cloned, new_child, new_label)?;
            } else {
                if self.has_same_children_except(
                    parent.node(),
                    parent.node(),
                    parent.edge(),
                    new_child,
                )? {
                    continue;
                }

                // we don't add a child to parent.edge() here.
                let cloned = self.clone_node(parent.node(), parent.edge(), false)?;

                let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

                builder.add_edge(cloned, new_child, new_label)?;

                let children_to_add: Vec<_> = builder
                    .children_of(parent.node())?
                    .skip(parent.edge() + 1)
                    .collect();

                for child in children_to_add {
                    builder.add_edge(cloned, child, new_label)?;
                }
            }
        }

        Ok(new_node)
    }

    /// Procedure for the new label:
    ///
    /// 1. Copy the old label.
    ///
    /// 2. Set the end to `pos`.
    ///
    /// 3. Pack the label.
    ///
    /// 4. Check if this label already exists.  If so, clone the label and
    /// return it.
    ///
    /// 5. Else set the label to be a plain label.
    ///
    /// 6. Check if this plain label already exists.  If so, clone the
    /// existing label, and return the clone of the cloned label.
    ///
    /// 7. Else return the plain label.
    ///
    /// # Fragment planting
    ///
    /// If the parameter `fragment` contains a fragment, that means we
    /// also check if an existing label is what we want by checking
    /// whether it has the same children except for the last one,
    /// whereas its last child contains the fragment as a prefix.
    ///
    /// Also, if an existing label is found to have exactly the same
    /// children, then for the sake of consistency, we plant the
    /// fragment under that existing node.
    fn create_new_label(
        &mut self,
        node: usize,
        end: Option<usize>,
        edge_index: usize,
        fragment: Option<(&DefaultForest<ForestLabel<GrammarLabel>>, bool)>,
    ) -> Result<Eon, Error> {
        let mut copied_label = self
            .vertex_label(node)?
            .ok_or(Error::NodeNoLabel(node))?
            .label();

        if let Some(pos) = end {
            copied_label.set_end(pos);
        } else {
            copied_label.open_end();
        }

        let label = ForestLabel::new(copied_label, ForestLabelType::Packed);

        if let Some(packed) = self.query_label(label) {
            for child in self.children_of(packed)? {
                let child_degree = self.degree(child)?;

                if self.has_same_children(child, node, child_degree, edge_index + 1)? {
                    if let Some((fragment, planted)) = fragment {
                        self.plant(child, fragment, planted)?;
                    }

                    return Ok(Eon::Ex(child));
                }

                if let Some((fragment, _planted)) = fragment {
                    let modified_degree = std::cmp::max(child_degree, 1) - 1;

                    // dbg!(node, end, edge_index, modified_degree);

                    // dbg!(child, child_degree);

                    // dbg!(&fragment);

                    if self.has_same_children(child, node, modified_degree, edge_index + 1)?
                        && child_degree != 0
                    {
                        let last_child = self.nth_child(child, child_degree - 1)?;

                        if self.is_prefix(last_child, fragment)? {
                            return Ok(Eon::Ex(child));
                        }
                    }
                }
            }

            let mut packed_children = self.children_of(packed)?;

            let first_child = packed_children.next().unwrap();

            let clone_index = self.clone_node(first_child, 0, true)?;

            let cloned_label = ForestLabel::new(copied_label, ForestLabelType::Cloned(clone_index));

            Ok(Eon::Nex(cloned_label))
        } else {
            let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);

            if let Some(existing) = self.query_label(plain_label) {
                let existing_degree = self.degree(existing)?;

                if self.has_same_children(existing, node, existing_degree, edge_index + 1)? {
                    if let Some((fragment, planted)) = fragment {
                        self.plant(existing, fragment, planted)?;
                    }

                    return Ok(Eon::Ex(existing));
                }

                if let Some((fragment, _planted)) = fragment {
                    let modified_degree = std::cmp::max(existing_degree, 1) - 1;

                    if existing_degree != 0
                        && self.has_same_children(
                            existing,
                            node,
                            modified_degree,
                            edge_index + 1,
                        )?
                    {
                        let last_child = self.nth_child(existing, existing_degree - 1)?;

                        if self.is_prefix(last_child, fragment)? {
                            return Ok(Eon::Ex(existing));
                        }
                    }
                }

                let clone_index = self.clone_node(existing, 0, true)?;

                Ok(Eon::Nex(ForestLabel::new(
                    copied_label,
                    ForestLabelType::Cloned(clone_index),
                )))
            } else {
                Ok(Eon::Nex(plain_label))
            }
        }
    }

    /// 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,
        nodea: usize,
        nodeb: usize,
        edge_num_a: usize,
        edge_num_b: usize,
    ) -> Result<bool, Error> {
        let children_a = self.children_of(nodea)?.take(edge_num_a);
        let children_b = self.children_of(nodeb)?.take(edge_num_b);

        if children_a.len() != children_b.len() {
            return Ok(false);
        }

        for (childa, childb) in children_a.zip(children_b) {
            if childa != childb {
                return Ok(false);
            }
        }

        Ok(true)
    }

    /// Detect if a node has a branch that has the same children as
    /// another node, until a given index, where it points to another
    /// given node.
    ///
    /// # Clones
    ///
    /// If `nodea` is a clone, it checks every clone to see if the
    /// condition is satisfied for some clone.
    fn has_same_children_until(
        &self,
        nodea: usize,
        nodeb: usize,
        edge_index: usize,
        alternative: usize,
    ) -> Result<bool, Error> {
        let labela = self.vertex_label(nodea)?.ok_or(Error::NodeNoLabel(nodea))?;
        let children_b = self.children_of(nodeb)?;

        if children_b.len() < edge_index + 1 {
            return Err(Error::IndexOutOfBounds(edge_index, children_b.len() - 1));
        }

        if labela.is_plain() {
            let children_a = self.children_of(nodea)?;

            if children_a.len() < edge_index + 1 {
                return Ok(false);
            }

            for (index, (childa, childb)) in
                children_a.zip(children_b).take(edge_index + 1).enumerate()
            {
                if index != edge_index {
                    if childa != childb {
                        return Ok(false);
                    }
                } else if childa != alternative {
                    return Ok(false);
                }
            }

            Ok(true)
        } else if labela.clone_index().is_some() {
            let mut parentsa = self.parents_of(nodea)?;

            assert_eq!(parentsa.len(), 1);

            let parenta = parentsa.next().unwrap().node();

            'branch_loop: for branch in self.children_of(parenta)? {
                let children_a = self.children_of(branch)?;
                let children_b = children_b.clone();

                if children_a.len() < edge_index + 1 {
                    continue 'branch_loop;
                }

                for (index, (childa, childb)) in
                    children_a.zip(children_b).take(edge_index + 1).enumerate()
                {
                    if index != edge_index {
                        if childa != childb {
                            continue 'branch_loop;
                        }
                    } else if childa != alternative {
                        continue 'branch_loop;
                    }
                }

                return Ok(true);
            }

            Ok(false)
        } else {
            // a packed node; this should not happen
            unreachable!("should not examine children of a packed node")
        }
    }

    /// Detect if a node has a branch that has the same children as
    /// another node, except for a given index, where it points to another
    /// given node.
    ///
    /// # Clones
    ///
    /// If `nodea` is a clone, it checks every clone to see if the
    /// condition is satisfied for some clone.
    fn has_same_children_except(
        &self,
        nodea: usize,
        nodeb: usize,
        edge_index: usize,
        alternative: usize,
    ) -> Result<bool, Error> {
        let labela = self.vertex_label(nodea)?.ok_or(Error::NodeNoLabel(nodea))?;
        let children_b = self.children_of(nodeb)?;

        if children_b.len() < edge_index + 1 {
            return Err(Error::IndexOutOfBounds(edge_index, children_b.len() - 1));
        }

        if labela.is_plain() {
            let children_a = self.children_of(nodea)?;

            if children_a.len() != children_b.len() {
                return Ok(false);
            }

            for (index, (childa, childb)) in
                children_a.zip(children_b).take(edge_index + 1).enumerate()
            {
                if index != edge_index {
                    if childa != childb {
                        return Ok(false);
                    }
                } else if childa != alternative {
                    return Ok(false);
                }
            }

            Ok(true)
        } else if labela.clone_index().is_some() {
            let mut parentsa = self.parents_of(nodea)?;

            assert_eq!(parentsa.len(), 1);

            let parenta = parentsa.next().unwrap().node();

            'branch_loop: for branch in self.children_of(parenta)? {
                let children_a = self.children_of(branch)?;
                let children_b = children_b.clone();

                if children_a.len() < children_b.len() {
                    continue 'branch_loop;
                }

                for (index, (childa, childb)) in
                    children_a.zip(children_b).take(edge_index + 1).enumerate()
                {
                    if index != edge_index {
                        if childa != childb {
                            continue 'branch_loop;
                        }
                    } else if childa != alternative {
                        continue 'branch_loop;
                    }
                }

                return Ok(true);
            }

            Ok(false)
        } else {
            // a packed node; this should not happen
            unreachable!("should not examine children of a packed node")
        }
    }
}

#[cfg(test)]
mod test_splone {
    use super::*;

    use grammar::TNT::*;

    fn create_test_forest(
    ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> {
        let mut forest = leaf!(GrammarLabel::new(Non(0), 0), GrammarLabel);

        forest.plant(
            0,
            leaf!(GrammarLabel::new_closed(6, 0, 1), GrammarLabel),
            false,
        )?;
        forest.plant(
            1,
            leaf!(GrammarLabel::new_closed(Ter(0), 0, 1), GrammarLabel),
            false,
        )?;

        forest.plant(0, leaf!(GrammarLabel::new(7, 1), GrammarLabel), false)?;
        forest.plant(3, leaf!(GrammarLabel::new(Non(0), 1), GrammarLabel), false)?;

        forest.plant(4, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?;
        forest.plant(5, leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel), false)?;

        forest.plant(
            6,
            leaf!(GrammarLabel::new_closed(11, 1, 2), GrammarLabel),
            false,
        )?;
        forest.plant(
            7,
            leaf!(GrammarLabel::new_closed(Ter(2), 1, 2), GrammarLabel),
            false,
        )?;

        forest.plant(
            6,
            leaf!(GrammarLabel::new_closed(13, 2, 3), GrammarLabel),
            false,
        )?;
        forest.plant(
            9,
            leaf!(GrammarLabel::new_closed(Ter(2), 2, 3), GrammarLabel),
            false,
        )?;

        forest.print_viz("test forest.gv")?;

        Ok(forest)
    }

    fn splone_6_3_1() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
    {
        let mut forest = create_test_forest()?;

        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);

        builder.set_label(
            5,
            ForestLabel::new(GrammarLabel::new_closed(3, 1, 3), ForestLabelType::Plain),
        )?;

        builder.set_label(
            6,
            ForestLabel::new(
                GrammarLabel::new_closed(Non(1), 1, 3),
                ForestLabelType::Plain,
            ),
        )?;

        Ok(forest)
    }

    fn splone_6_2_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
    {
        let mut forest = splone_6_3_1()?;

        let cloned = forest.clone_node(4, 0, false)?;

        forest.plant(
            cloned,
            leaf!(GrammarLabel::new_closed(3, 1, 2), GrammarLabel),
            false,
        )?;

        forest.plant(
            cloned + 1,
            leaf!(GrammarLabel::new_closed(Non(1), 1, 2), GrammarLabel),
            false,
        )?;

        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);

        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));

        builder.add_edge(cloned + 2, 7, dummy_label)?;

        Ok(forest)
    }

    fn splone_6_n_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
    {
        let mut forest = splone_6_2_0()?;

        let cloned = forest.clone_node(4, 0, false)?;

        forest.plant(cloned, leaf!(GrammarLabel::new(3, 1), GrammarLabel), false)?;

        forest.plant(
            cloned + 1,
            leaf!(GrammarLabel::new(Non(1), 1), GrammarLabel),
            false,
        )?;

        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);

        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));

        builder.add_edge(cloned + 2, 7, dummy_label)?;

        Ok(forest)
    }

    fn splone_4_3_0() -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>>
    {
        let mut forest = splone_6_n_0()?;

        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),
            false,
        )?;

        forest.plant(
            cloned + 1,
            leaf!(GrammarLabel::new_closed(Non(0), 1, 3), GrammarLabel),
            false,
        )?;

        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);

        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));

        builder.add_edge(cloned + 2, 5, dummy_label)?;

        Ok(forest)
    }

    fn splone_17_3_0_15_3_0(
    ) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, Box<dyn std::error::Error>> {
        let mut forest = splone_4_3_0()?;

        let to_clone = forest
            .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(1), 1, 3)))
            .unwrap();

        let cloned = forest.clone_node(to_clone, 0, false)?;

        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);

        let dummy_label = ForestLabel::from(GrammarLabel::new(0, 0));

        let child = builder
            .query_label(ForestLabel::from(GrammarLabel::new_closed(11, 1, 2)))
            .unwrap();

        builder.add_edge(cloned, child, dummy_label)?;

        let to_clone = forest
            .query_label(ForestLabel::from(GrammarLabel::new_closed(Non(0), 1, 3)))
            .unwrap();

        let cloned = forest.clone_node(to_clone, 0, false)?;

        let mut builder = PLGBuilderMut::from_graph_mut(&mut forest.graph);

        let child = builder
            .query_label(ForestLabel::from(GrammarLabel::new(3, 1)))
            .unwrap();

        builder.add_edge(cloned, child, dummy_label)?;

        Ok(forest)
    }

    #[test]
    fn test() -> Result<(), Box<dyn std::error::Error>> {
        let mut test_forest = create_test_forest()?;

        test_forest.splone(6, Some(3), 1, false)?;

        let answer = splone_6_3_1()?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 6 3 1.gv")?;
            panic!("splone(6, Some(3), 1) produced wrong forest");
        }

        test_forest.splone(6, Some(3), 1, false)?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 6 3 1.gv")?;
            panic!("repeated splone(6, Some(3), 1) produced wrong forest");
        }

        test_forest.splone(6, Some(2), 0, false)?;

        let answer = splone_6_2_0()?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 6 2 0.gv")?;
            panic!("splone(6, Some(2), 0) produced wrong forest");
        }

        test_forest.splone(6, Some(2), 0, false)?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 6 2 0.gv")?;
            panic!("repeated splone(6, Some(2), 0) produced wrong forest");
        }

        test_forest.splone(6, None, 0, false)?;

        let answer = splone_6_n_0()?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 6 None 0.gv")?;
            panic!("splone(6, None, 0) produced wrong forest");
        }

        test_forest.splone(14, None, 0, false)?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 6 None 0.gv")?;
            panic!("repeated splone(6, None, 0) produced wrong forest");
        }

        test_forest.splone(4, Some(3), 0, false)?;

        let answer = splone_4_3_0()?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 4 3 0.gv")?;
            panic!("splone(4, Some(3), 0) produced wrong forest");
        }

        test_forest.splone(4, Some(3), 0, false)?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 4 3 0.gv")?;
            panic!("repeated splone(4, Some(3), 0) produced wrong forest");
        }

        test_forest.splone(17, Some(3), 0, false)?;
        test_forest.splone(15, Some(3), 0, false)?;

        let answer = splone_17_3_0_15_3_0()?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 17 3 0 15 3 0.gv")?;
            panic!("splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest");
        }

        test_forest.splone(17, Some(3), 0, false)?;
        test_forest.splone(15, Some(3), 0, false)?;

        if test_forest != answer {
            test_forest.print_viz("sploned forest.gv")?;
            answer.print_viz("splone 17 3 0 15 3 0.gv")?;
            panic!(
                "repeated splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest"
            );
        }

        Ok(())
    }
}