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

        // if node == 15 {
        //     dbg!(end, new_label, node_label);
        // }

        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_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_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);

            parent_label.set_end_option(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. If the new node is closed or if the new node is not cloned,
    /// then 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>,
        old_label: ForestLabel<GrammarLabel>,
        mut node: usize,
        edge_index: usize,
        completingp: bool,
    ) -> Result<usize, Error> {
        let end = new_label.label().end();
        let new_node_is_clone = new_label.clone_index().is_some();

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

        let new_node = builder.add_vertex(new_label);

        let new_packed = if new_node_is_clone {
            let packed = builder
                .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed))
                .unwrap_or_else(|| panic!("A cloned node {new_node} without packed nodes"));

            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)?;
        }

        // NOTE: If the label of the parent is closed while the node
        // label is open ended, we need to use an opened parent
        // instead.
        //
        // To be specific, we only need to split the parent if the new
        // label is closed.  This can be seen from the fact that this
        // function only deals with the situation that the new label
        // and the old label are different.  In this situation, if the
        // new label is closed, it means we are closing a node under
        // an open node, and we need to clone that parent indeed.  On
        // the other hand, if we are opening a node under a closed
        // node, that parent does not need to connect to this new
        // node.

        if end.is_none() && new_node_is_clone {
            return Ok(new_node);
        }

        // We actually have to consider two cases here: one when the
        // new end is closed, and the other when the new end is open
        // and the new node is a plain node.
        //
        // The former case can be dealt with by cloning the parent,
        // whereas the latter needs to open the parents recursively
        // until it meets an open node.

        if old_label.clone_index().is_some() {
            let mut parents = self.parents_of(node)?;
            assert_eq!(parents.len(), 1);
            node = parents.next().unwrap().node();
        }

        self.split_parents(
            node,
            old_label,
            end,
            new_packed.unwrap_or(new_node),
            completingp,
        )?;

        Ok(new_node)
    }

    /// Procedure for the new label:
    ///
    /// 1. Copy the old label.
    ///
    /// 2. Set the end to `end`.
    ///
    /// 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();

        copied_label.set_end_option(end);

        let packed_label = ForestLabel::new(copied_label, ForestLabelType::Packed);
        let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);

        let root = if let Some(root) = self.root() {
            root
        } else {
            return Ok(Eon::Nex(plain_label));
        };

        let packed_query = self.query_label(packed_label);

        // We ignore nodes without parents which are not roots.
        if matches!(packed_query, Some(packed) if packed == root ||
                    self.parents_of(packed)?.len() > 0)
        {
            // this is safe because of the 'if' guard
            let packed = packed_query.unwrap();

            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_query = self.query_label(plain_label);

            if matches!(plain_query, Some(plain) if plain == root ||
                        self.parents_of(plain)?.len() > 0)
            {
                let existing = plain_query.unwrap();

                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 node_children = self.children_of(node)?;

            let mut parents = self.parents_of(node)?;

            #[cfg(debug_assertions)]
            assert_eq!(parents.len(), 1, "Assumption fails");

            let packed = parents.next().unwrap().node();

            'clone_loop: for clone in self.children_of(packed)? {
                let degree = self.degree(clone)?;

                if degree == 0 {
                    return Ok(Some(clone));
                }

                if degree <= edge_index {
                    continue;
                }

                if clone != node {
                    for (clone_child, child) in self
                        .children_of(clone)?
                        .zip(node_children.clone())
                        .take(edge_index + 1)
                    {
                        if clone_child != child {
                            continue 'clone_loop;
                        }
                    }
                }

                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))
    }

    /// Split the parents of `node`.
    ///
    /// We have created a new node `new_node`, and now we want to
    /// adjoin it to /proper/ parents so that the labels of parents
    /// match.
    ///
    /// In particular, the rule parents of the old node should have
    /// the new counter-parts and should be parents of the new node.
    ///
    /// Moreover, if the new label is open, we demand that every
    /// ancestor of the new node be open as well, as a closed node
    /// cannot contain an open node by definition.
    fn split_parents(
        &mut self,
        node: usize,
        label: ForestLabel<GrammarLabel>,
        end: Option<usize>,
        new_node: usize,
        completingp: bool,
    ) -> Result<(), Error> {
        // First handle the rule parents.

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

        let mut ancestors: Vec<(Parent, usize)> = Vec::with_capacity(
            parents
                .iter()
                .copied()
                .map(|parent| self.parents_of(parent).map_or(0, |iter| iter.len()))
                .sum(),
        );

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

            #[cfg(debug_assertions)]
            {
                assert!(
                    matches!(parent_label.label(), GrammarLabelType::Rule(_)),
                    "this should be a rule parent"
                );

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

                    panic!("a rule node should not have more than one child");
                }
            }

            parent_label.set_end_option(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);

            builder.add_edge(new_parent, new_node, label)?;

            // Open all closed parents if necessary.
            // dbg!(new_node, label, parent, new_parent, end);

            if end.is_none() {
                let opened = self.open_ancestors(parent, new_parent)?;

                // dbg!(&opened);

                ancestors.extend(opened);
            } else {
                ancestors.extend(
                    self.parents_of(parent)?
                        .map(|parent_parent| (parent_parent, new_parent)),
                );
            }
        }

        // Now clone and add edges, if necessary.

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

                // we add no child to parent.edge()-th child here.
                let cloned = self.clone_node(parent.node(), parent.edge(), false)?;

                // dbg!(cloned, parent, new_child);

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

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

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

        Ok(())
    }

    /// Open all closed ancestors.
    fn open_ancestors(
        &mut self,
        parent: usize,
        new_parent: usize,
    ) -> Result<Vec<(Parent, usize)>, Error> {
        let mut result = Vec::new();

        let mut stack: Vec<_> = vec![(parent, new_parent)];

        while let Some((top, new_top)) = stack.pop() {
            // dbg!(top, new_top);
            let parents: Vec<_> = self.parents_of(top)?.collect();

            'parent_loop: for parent in parents {
                // dbg!(parent);

                let parent_node = parent.node();
                let parent_edge = parent.edge();
                let parent_label = self
                    .vertex_label(parent_node)?
                    .ok_or(Error::NodeNoLabel(parent_node))?
                    .label();

                if parent_label.end().is_some() {
                    let new_label = self.create_new_label(parent_node, None, parent_edge, None)?;

                    let new_label = match new_label {
                        Eon::Nex(label) => label,
                        Eon::Ex(ex_node) => {
                            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

                            builder.add_edge(ex_node, new_top, parent_label.into())?;

                            continue 'parent_loop;
                        }
                    };

                    let new_node_is_clone = new_label.clone_index().is_some();

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

                    let new_node = builder.add_vertex(new_label);

                    let new_packed = if new_node_is_clone {
                        let packed = builder
                            .query_label(ForestLabel::new(
                                new_label.label(),
                                ForestLabelType::Packed,
                            ))
                            .unwrap_or_else(|| {
                                panic!("A cloned node {new_node} without packed nodes")
                            });

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

                        Some(packed)
                    } else {
                        builder.add_edge(new_node, new_top, new_label)?;
                        None
                    };

                    let preserve_children: Vec<_> = builder
                        .children_of(parent_node)?
                        .take(parent_edge)
                        .collect();

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

                    if new_node_is_clone {
                        continue 'parent_loop;
                    }

                    // Now deal with new rule parents.

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

                    for rule_parent in rule_parents {
                        let mut rule_parent_label = self
                            .vertex_label(rule_parent)?
                            .ok_or(Error::NodeNoLabel(rule_parent))?
                            .label();

                        #[cfg(debug_assertions)]
                        {
                            assert!(
                                matches!(rule_parent_label.label(), GrammarLabelType::Rule(_)),
                                "this should be a rule parent"
                            );

                            if self.degree(rule_parent)? != 1 {
                                dbg!(rule_parent);
                                let _ = self.print_viz("dbg forest.gv");

                                panic!("a rule node should not have more than one child");
                            }
                        }

                        rule_parent_label.set_end_option(None);

                        let parent_label = ForestLabel::from(rule_parent_label);

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

                        let new_rule_parent = builder.add_vertex(parent_label);

                        builder.add_edge(
                            new_rule_parent,
                            new_packed.unwrap_or(new_node),
                            parent_label,
                        )?;

                        stack.push((rule_parent, new_rule_parent));
                    }
                } else {
                    result.push((parent, new_top));
                }
            }
        }

        Ok(result)
    }

    /// 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(())
    }
}