#![debugger_visualizer(gdb_script_file = "printer.py")]
//! This module provides a default implementation of iten derivation
//! forest.

use super::*;
use crate::atom::{default::DefaultAtom, Atom};
use grammar::{GrammarLabel, GrammarLabelType, TNT};
use graph::{
    builder::BuilderMut, labelled::binary::PLGBuilderMut, Graph, LabelGraph, PLGraph, RedirectGraph,
};

use graph_macro::Graph;

use std::fmt::Display;

/// The type of errors for forest operations.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)]
pub enum Error {
    /// An index is out of bounds.
    ///
    /// The first component is the index that is out of bounds, and
    /// the second component is the current length of nodes.
    IndexOutOfBounds(usize, usize),
    /// The forest does not permit duplicate nodes but encounters a
    /// repeated node.
    DuplicatedNode(usize),
    /// A node has no labels while it is required to have one.
    NodeNoLabel(usize),
    /// Encounter an invalid error in converting from an error of
    /// graphs.
    InvalidGraphError(GError),
    /// Encounter an error when converting forest labels.
    LabelConversion(ForestLabelError),
    /// Trying to split a packed node.
    SplitPack(usize),
    /// A cloned node should have exactly one parent.
    InvalidClone(usize),
}

impl Display for Error {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::IndexOutOfBounds(index, bound) => {
                write!(f, "index {index} is out of bound {bound}")
            }
            Error::DuplicatedNode(n) => write!(f, "node {n} is duplicated"),
            Error::InvalidGraphError(ge) => write!(f, "invalid error: {ge}"),
            Error::NodeNoLabel(n) => write!(f, "node {n} has no labels, but it should have one"),
            Error::LabelConversion(le) => write!(f, "fail to convert labels: {le}"),
            Error::SplitPack(n) => write!(f, "cannot split the packed node {n}"),
            Error::InvalidClone(n) => {
                write!(f, "the cloned node {n} should have exactly one parent")
            }
        }
    }
}

impl std::error::Error for Error {}

impl From<GError> for Error {
    fn from(ge: GError) -> Self {
        match ge {
            GError::IndexOutOfBounds(index, bound) => Self::IndexOutOfBounds(index, bound),
            GError::DuplicatedNode(n) => Self::DuplicatedNode(n),
            _ => Self::InvalidGraphError(ge),
        }
    }
}

impl From<ForestLabelError> for Error {
    fn from(le: ForestLabelError) -> Self {
        Self::LabelConversion(le)
    }
}

// FIXME: Provide a better Debug implementation.

/// A default implementation of forest.
#[derive(Debug, Clone, Graph)]
pub struct DefaultForest<T: GraphLabel> {
    pub(crate) graph: PLGraph<T>,
    root: Option<usize>,
}

impl<T: GraphLabel> Default for DefaultForest<T> {
    fn default() -> Self {
        let graph = Default::default();
        let root = None;

        Self { graph, root }
    }
}

impl<T: GraphLabel> AsRef<DefaultForest<T>> for DefaultForest<T> {
    fn as_ref(&self) -> &DefaultForest<T> {
        self
    }
}

impl<T: GraphLabel> ParentsGraph for DefaultForest<T> {
    type Iter<'a>= <PLGraph<T> as ParentsGraph>::Iter<'a>
    where
        Self:'a;

    #[inline]
    fn parents_of(&self, node_id: usize) -> Result<<Self as ParentsGraph>::Iter<'_>, GError> {
        self.graph.parents_of(node_id)
    }

    #[inline]
    fn nth_child(&self, node_id: usize, n: usize) -> Result<usize, GError> {
        self.graph.nth_child(node_id, n)
    }

    #[inline]
    fn edge_to_parent(
        &self,
        source: usize,
        target: usize,
    ) -> Result<Option<graph::Parent>, GError> {
        self.graph.edge_to_parent(source, target)
    }
}

impl<T: GraphLabel> LabelGraph<T> for DefaultForest<T> {
    type Iter<'a> = std::iter::Empty<usize>
    where
        Self: 'a;

    type LabelIter<'a> = std::iter::Empty<(&'a T, <Self as LabelGraph<T>>::Iter<'a>)>
    where
        Self: 'a,
        T: 'a;

    type EdgeLabelIter<'a> = std::iter::Empty<T>
    where
        Self: 'a,
        T: 'a;

    #[inline]
    fn query_label(&self, label: T) -> Option<usize> {
        self.graph.query_label(label)
    }

    #[inline]
    fn vertex_label(&self, node_id: usize) -> Result<Option<T>, GError> {
        self.graph.vertex_label(node_id)
    }

    fn edge_label(
        &self,
        _source: usize,
        _target: usize,
    ) -> Result<Self::EdgeLabelIter<'_>, GError> {
        unimplemented!("edges have no labels")
    }

    fn find_children_with_label(
        &self,
        _node_id: usize,
        _label: &T,
    ) -> Result<<Self as LabelGraph<T>>::Iter<'_>, GError> {
        unimplemented!("edges have no labels")
    }

    fn labels_of(&self, _node_id: usize) -> Result<Self::LabelIter<'_>, GError> {
        unimplemented!("edges have no labels")
    }

    fn has_edge_label(&self, _node_id: usize, _label: &T, _target: usize) -> Result<bool, GError> {
        unimplemented!("edges have no labels")
    }
}

impl<T: GraphLabel> Forest<T> for DefaultForest<ForestLabel<T>> {
    type Error = Error;

    fn root(&self) -> Option<usize> {
        self.root
    }

    fn new_leaf(label: T) -> Self {
        let mut graph = PLGraph::default();

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

        let root = Some(builder.add_vertex(ForestLabel::from(label)));

        Self { graph, root }
    }

    fn transform_label(
        &mut self,
        node_id: usize,
        transform: impl FnOnce(T) -> T,
    ) -> Result<(), Self::Error> {
        let vertex_label = self
            .vertex_label(node_id)?
            .ok_or(Error::NodeNoLabel(node_id))?;

        let transformed_label = transform(vertex_label.label());

        let transformed_label = ForestLabel::new(transformed_label, vertex_label.status);

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

        builder
            .set_label(node_id, transformed_label)
            .map_err(Into::into)
    }

    fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
    where
        F: Borrow<Self>,
    {
        if !self.has_node(node_id) {
            return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
        }

        let fragment = fragment.borrow();
        let fragment_nodes_len = fragment.nodes_len();

        let frag_root = if let Some(root) = fragment.root() {
            root
        } else {
            // an empty forest is a prefix of any forest.
            return Ok(true);
        };

        // We assign to each node in the fragment the node id in the
        // forest that has a label that corresponds to the label of
        // the node.  One thing to note is that a plain node can also
        // correspond to a packed node, but a packed node cannot
        // correspond to a plain node.  Denote this correspondence as
        // A -> f(A).
        //
        // After this, we need to check, for each edge from A to B, if
        // f(A) has an edge to f(B).  But there are some caveats: if A
        // is a packed node and B is a cloned node, we check nothing.
        // And if f(A) is a packed node, we check every of its cloned
        // children to see if it has an edge to f(B).  Finally, we
        // evaluate the fragment as a boolean expression, where the
        // only operation is multiplication and the final value is the
        // return value of the function.
        //
        // I have a marvelous proof that this algorithm works, but my
        // computer does not have enough memory to contain this proof.
        // See
        // <https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Fermat's_conjecture>.

        // The vector of correspondance `f`.
        let mut correspondance: Vec<usize> =
            std::iter::repeat(0).take(fragment_nodes_len).collect();

        for (node, cor_mut) in (0..fragment_nodes_len).zip(correspondance.iter_mut()) {
            let frag_label = fragment
                .vertex_label(node)?
                .ok_or(Error::NodeNoLabel(node))?
                .label();

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

            if let Some(packed_pos) = self.query_label(packed_label) {
                *cor_mut = packed_pos;
            } else if let Some(plain_pos) = self.query_label(plain_label) {
                *cor_mut = plain_pos;
            } else {
                return Ok(false);
            }
        }

        let correspondance = correspondance;

        let f_root = correspondance
            .get(frag_root)
            .copied()
            .ok_or(Error::IndexOutOfBounds(frag_root, correspondance.len()))?;

        if f_root != node_id {
            return Ok(false);
        }

        'node_loop: for (node, f_node) in
            (0..fragment_nodes_len).zip(correspondance.iter().copied())
        {
            let node_label = fragment
                .vertex_label(node)?
                .ok_or(Error::NodeNoLabel(node))?;
            let node_degree = fragment.degree(node)?;

            let f_label = self
                .vertex_label(f_node)?
                .ok_or(Error::NodeNoLabel(f_node))?;

            if node_label.is_packed() {
                let value = f_label.is_packed() && self.degree(f_node)? >= node_degree;

                if !value {
                    return Ok(false);
                }

                continue 'node_loop;
            }

            if f_label.is_packed() {
                let mut value = false;

                'f_children_loop: for f_node_child in self.children_of(f_node)? {
                    if self.degree(f_node_child)? < node_degree {
                        continue 'f_children_loop;
                    }

                    for (child, f_node_child_child) in fragment
                        .children_of(node)?
                        .zip(self.children_of(f_node_child)?)
                    {
                        let f_child = correspondance
                            .get(child)
                            .copied()
                            .ok_or(Error::IndexOutOfBounds(child, correspondance.len()))?;

                        if f_node_child_child != f_child {
                            continue 'f_children_loop;
                        }
                    }

                    value = true;

                    break 'f_children_loop;
                }

                if !value {
                    return Ok(false);
                }

                continue 'node_loop;
            }

            if self.degree(f_node)? < node_degree {
                return Ok(false);
            }

            for (child, f_node_child) in fragment.children_of(node)?.zip(self.children_of(f_node)?)
            {
                let f_child = correspondance
                    .get(child)
                    .copied()
                    .ok_or(Error::IndexOutOfBounds(child, correspondance.len()))?;

                if f_node_child != f_child {
                    return Ok(false);
                }
            }
        }

        Ok(true)
    }

    fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
    where
        F: Borrow<Self>,
    {
        // As in the method `is_prefix`, we assign a node id of self
        // to a node in the fragment.  Here a plain node can
        // correspond to a packed node, and a packed node can also
        // correspond to a plain node.  The only restriction is that
        // if there is a packed node in the self forest, then it must
        // be corresponded, rather than the plain node with the same
        // inner label.  One thing to note is that this correspondance
        // is not fixed during the execution of the function.
        // Instead, the planting of the function will change the
        // status of nodes.  And if the fragment contains nodes that
        // share children, then the status of nodes need to be
        // synchronized after each change.
        //
        // Another way is to give up calculating the status
        // beforehand.  Rather, we calculate the correspondance
        // exactly when we need it.  This might turn out to be much
        // simpler and more efficient.
        //
        // After this, consider a correspondence pair (node, f(node)),
        // there are five situations to consider:
        //
        // 1. f(node) is non-existent: in this case we just add a new
        // node f(node) and add edges from f(node) to f(child) for
        // every child of node.
        //
        // 2. node and f(node) are not packed: We need to decide
        // whether f(node) should be cloned.
        //
        // 3. node is packed but f(node) is not: in this case we need
        // to clone f(node), and for each cloned child of node, we
        // need to decide whether it needs to be added as a new node.
        //
        // 4. node is not packed but f(node) is: in this case we check
        // if there is a cloned child of f(node) that possesses the
        // same set of children as node, as a prefix.  If, and only
        // if, this is not the case, we add a new clone with the given
        // children.
        //
        // 5. both node and f(node) are packed: in this case we repeat
        // the same process as the previous situation, for each cloned
        // child of node.

        if !self.has_node(node_id) {
            return Err(Error::IndexOutOfBounds(node_id, self.nodes_len()));
        }

        let fragment = fragment.borrow();

        let fragment_nodes_len = fragment.nodes_len();

        let root = if let Some(root) = fragment.root() {
            root
        } else {
            // Nothing to plant.
            return Ok(());
        };

        // A convenient function to calculate the correspondance.
        fn builder_query<T: GraphLabel>(
            builder: &PLGBuilderMut<ForestLabel<T>>,
            label: T,
        ) -> Option<(usize, ForestLabel<T>, bool)> {
            let packed_label = ForestLabel::new(label, ForestLabelType::Packed);
            let plain_label = ForestLabel::new(label, ForestLabelType::Plain);

            if let Some(packed_node) = builder.query_label(packed_label) {
                Some((packed_node, packed_label, true))
            } else {
                builder
                    .query_label(plain_label)
                    .map(|plain_node| (plain_node, plain_label, false))
            }
        }

        // A convenient function to decide whether a node in the
        // fragment matches the corresponding node in the builder.
        fn children_match_p<T: GraphLabel>(
            builder: &PLGBuilderMut<ForestLabel<T>>,
            nodea: usize,
            fragment: &DefaultForest<ForestLabel<T>>,
            nodeb: usize,
        ) -> Result<bool, Error> {
            if builder.degree(nodea)? < fragment.degree(nodeb)? {
                return Ok(false);
            }

            for (frag_child, builder_child) in fragment
                .children_of(nodeb)?
                .zip(builder.children_of(nodea)?)
            {
                let frag_label = fragment
                    .vertex_label(frag_child)?
                    .ok_or(Error::NodeNoLabel(frag_child))?
                    .label();
                let builder_label = builder
                    .vertex_label(builder_child)?
                    .ok_or(Error::NodeNoLabel(builder_child))?
                    .label();

                if frag_label != builder_label {
                    return Ok(false);
                }
            }

            Ok(true)
        }

        // If the fragment has been planted before, we just add an
        // edge.

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

        let root_label = fragment
            .vertex_label(root)?
            .ok_or(Error::NodeNoLabel(root))?;

        let f_root_label_packed = builder_query(&builder, root_label.label());

        if let Some((f_root, f_label, _)) = f_root_label_packed {
            if f_root != node_id {
                builder.add_edge(node_id, f_root, f_label)?;
            }
        } else {
            let f_root =
                builder.add_vertex(ForestLabel::new(root_label.label(), ForestLabelType::Plain));

            builder.add_edge(node_id, f_root, root_label)?;
        }

        if planted {
            return Ok(());
        }

        'node_loop: for node in 0..fragment_nodes_len {
            let node_label = fragment
                .vertex_label(node)?
                .ok_or(Error::NodeNoLabel(node))?;

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

            let f_node_label_packed = builder_query(&builder, node_label.label());

            if let Some((f_node, _f_label, f_packed)) = f_node_label_packed {
                match (node_label.is_packed(), f_packed) {
                    (false, false) => {
                        // case 2

                        if builder.is_empty_node(f_node)? {
                            for child in fragment.children_of(node)? {
                                let child_label = fragment
                                    .vertex_label(child)?
                                    .ok_or(Error::NodeNoLabel(child))?
                                    .label();

                                if let Some((f_child, _, _)) = builder_query(&builder, child_label)
                                {
                                    builder.add_edge(f_node, f_child, node_label)?;
                                } else {
                                    let f_child = builder.add_vertex(ForestLabel::new(
                                        child_label,
                                        ForestLabelType::Plain,
                                    ));
                                    builder.add_edge(f_node, f_child, node_label)?;
                                }
                            }
                        } else if !children_match_p(&builder, f_node, fragment.borrow(), node)? {
                            let cloned = self.clone_node(f_node, 0, false)?;

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

                            for child in fragment.children_of(node)? {
                                let child_label = fragment
                                    .vertex_label(child)?
                                    .ok_or(Error::NodeNoLabel(child))?
                                    .label();

                                if let Some((f_child, _, _)) = builder_query(&builder, child_label)
                                {
                                    builder.add_edge(cloned, f_child, node_label)?;
                                } else {
                                    let f_child = builder.add_vertex(ForestLabel::new(
                                        child_label,
                                        ForestLabelType::Plain,
                                    ));
                                    builder.add_edge(cloned, f_child, node_label)?;
                                }
                            }
                        }
                    }
                    (true, false) => {
                        // case 3

                        if builder.is_empty_node(f_node)? {
                            for cloned_child in fragment.children_of(node)? {
                                let cloned = self.clone_node(f_node, 0, false)?;

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

                                for child in fragment.children_of(cloned_child)? {
                                    let child_label = fragment
                                        .vertex_label(child)?
                                        .ok_or(Error::NodeNoLabel(child))?;

                                    let f_child = builder_query(&builder, child_label.label());

                                    if let Some((f_child, _, _)) = f_child {
                                        builder.add_edge(cloned, f_child, child_label)?;
                                    } else {
                                        let f_child = builder.add_vertex(ForestLabel::new(
                                            child_label.label(),
                                            ForestLabelType::Plain,
                                        ));

                                        builder.add_edge(cloned, f_child, child_label)?;
                                    }
                                }
                            }

                            continue 'node_loop;
                        }

                        for cloned_child in fragment.children_of(node)? {
                            let builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

                            if !children_match_p(&builder, f_node, fragment.borrow(), cloned_child)?
                            {
                                let cloned = self.clone_node(f_node, 0, false)?;

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

                                for child in fragment.children_of(cloned_child)? {
                                    let child_label = fragment
                                        .vertex_label(child)?
                                        .ok_or(Error::NodeNoLabel(child))?;

                                    let f_child = builder_query(&builder, child_label.label());

                                    if let Some((f_child, _, _)) = f_child {
                                        builder.add_edge(cloned, f_child, child_label)?;
                                    } else {
                                        let f_child = builder.add_vertex(ForestLabel::new(
                                            child_label.label(),
                                            ForestLabelType::Plain,
                                        ));

                                        builder.add_edge(cloned, f_child, child_label)?;
                                    }
                                }
                            }
                        }
                    }
                    (false, true) => {
                        // case 4

                        let mut f_node_cloned_child = None;

                        for f_node_clone in builder.children_of(f_node)? {
                            f_node_cloned_child = Some(f_node_clone);

                            if builder.is_empty_node(f_node_clone)? {
                                for child in fragment.children_of(node)? {
                                    let child_label = fragment
                                        .vertex_label(child)?
                                        .ok_or(Error::NodeNoLabel(child))?;

                                    let f_child = builder_query(&builder, child_label.label());

                                    if let Some((f_child, _, _)) = f_child {
                                        builder.add_edge(f_node_clone, f_child, child_label)?;
                                    } else {
                                        let f_child = builder.add_vertex(ForestLabel::new(
                                            child_label.label(),
                                            ForestLabelType::Plain,
                                        ));

                                        builder.add_edge(f_node_clone, f_child, child_label)?;
                                    }
                                }

                                continue 'node_loop;
                            }

                            if children_match_p(&builder, f_node_clone, fragment.borrow(), node)? {
                                continue 'node_loop;
                            }
                        }

                        let f_node_cloned_child = if let Some(clone) = f_node_cloned_child {
                            clone
                        } else {
                            continue 'node_loop;
                        };

                        let cloned = self.clone_node(f_node_cloned_child, 0, false)?;

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

                        for child in fragment.children_of(node)? {
                            let child_label = fragment
                                .vertex_label(child)?
                                .ok_or(Error::NodeNoLabel(child))?;

                            let f_child = builder_query(&builder, child_label.label());

                            if let Some((f_child, _, _)) = f_child {
                                builder.add_edge(cloned, f_child, child_label)?;
                            } else {
                                let f_child = builder.add_vertex(ForestLabel::new(
                                    child_label.label(),
                                    ForestLabelType::Plain,
                                ));

                                builder.add_edge(cloned, f_child, child_label)?;
                            }
                        }
                    }
                    (true, true) => {
                        // case 5

                        'cloned_loop: for cloned_child in fragment.children_of(node)? {
                            let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

                            let mut f_node_cloned_child = None;

                            for f_node_clone in builder.children_of(f_node)? {
                                f_node_cloned_child = Some(f_node_clone);

                                if builder.is_empty_node(f_node_clone)? {
                                    for child in fragment.children_of(cloned_child)? {
                                        let child_label = fragment
                                            .vertex_label(child)?
                                            .ok_or(Error::NodeNoLabel(child))?;

                                        let f_child = builder_query(&builder, child_label.label());

                                        if let Some((f_child, _, _)) = f_child {
                                            builder.add_edge(f_node_clone, f_child, child_label)?;
                                        } else {
                                            let f_child = builder.add_vertex(ForestLabel::new(
                                                child_label.label(),
                                                ForestLabelType::Plain,
                                            ));

                                            builder.add_edge(f_node_clone, f_child, child_label)?;
                                        }
                                    }

                                    continue 'node_loop;
                                }

                                if children_match_p(
                                    &builder,
                                    f_node_clone,
                                    fragment.borrow(),
                                    cloned_child,
                                )? {
                                    continue 'cloned_loop;
                                }
                            }

                            let f_node_cloned_child = if let Some(clone) = f_node_cloned_child {
                                clone
                            } else {
                                continue 'cloned_loop;
                            };

                            let cloned = self.clone_node(f_node_cloned_child, 0, false)?;

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

                            for child in fragment.children_of(cloned_child)? {
                                let child_label = fragment
                                    .vertex_label(child)?
                                    .ok_or(Error::NodeNoLabel(child))?;

                                let f_child = builder_query(&builder, child_label.label());

                                if let Some((f_child, _, _)) = f_child {
                                    builder.add_edge(cloned, f_child, child_label)?;
                                } else {
                                    let f_child = builder.add_vertex(ForestLabel::new(
                                        child_label.label(),
                                        ForestLabelType::Plain,
                                    ));

                                    builder.add_edge(cloned, f_child, child_label)?;
                                }
                            }
                        }
                    }
                }
            } else {
                // case 1

                let f_node = builder
                    .add_vertex(ForestLabel::new(node_label.label(), ForestLabelType::Plain));

                for child in fragment.children_of(node)? {
                    if child == node {
                        continue;
                    }

                    let child_label_label = fragment
                        .vertex_label(child)?
                        .ok_or(Error::NodeNoLabel(child))?
                        .label();

                    let f_child_label_packed = builder_query(&builder, child_label_label);

                    if let Some((f_child, _, _)) = f_child_label_packed {
                        builder.add_edge(f_node, f_child, node_label)?;
                    } else {
                        let plain_label =
                            ForestLabel::new(child_label_label, ForestLabelType::Plain);

                        let f_child = builder.add_vertex(plain_label);

                        builder.add_edge(f_node, f_child, node_label)?;
                    }
                }
            }
        }

        Ok(())
    }

    fn clone_node(
        &mut self,
        node_id: usize,
        preserved_edges_num: usize,
        no_new_clone: bool,
    ) -> Result<usize, Self::Error> {
        let builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

        let old_label = builder
            .vertex_label(node_id)?
            .ok_or(Error::NodeNoLabel(node_id))?;

        if old_label.is_packed() {
            dbg!(node_id, old_label);
            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
            .clone::<DefaultForest<ForestLabel<T>>>(self.borrow())
            .unwrap();

        if old_label.clone_index().is_some() {
            if no_new_clone {
                return Ok(new_label.clone_index().unwrap());
            }

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

            // Make sure it only has one parent, which is the
            // representative node.
            assert_eq!(parents.len(), 1);

            // We checked its length is 1, so it is safe to unwrap
            // here.
            let rep_node = parents.next().unwrap().node();

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

            let new_clone = builder.add_vertex(new_label);

            builder.add_edge(rep_node, new_clone, new_label)?;

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

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

            return Ok(new_clone);
        }

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

        // We are sure old_label is not a clone here, so it is safe to
        // unwrap.
        let rep_label = old_label.pack().unwrap();

        // 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
        // node, otherwise that edge will be redirected as well.

        // Unfortunately I cannot loop through parents and mutate them
        // at the same time, so I first collect them into a vector.
        let parents: Vec<_> = builder.parents_of(node_id)?.collect();

        for parent in parents.into_iter() {
            builder.redirect(parent.node(), parent.edge(), new_index)?;
        }

        // Point the new node to the old node.  OLD_LABEL is just a
        // place holder.

        builder.add_edge(new_index, node_id, old_label)?;

        // Modify the label of the old node.

        builder.set_label(node_id, new_label)?;

        // Make another clone

        // new_label is cloned, so is guaranteed not to be packed, and
        // we are safe to unwrap.
        let new_label = new_label
            .clone::<DefaultForest<ForestLabel<T>>>(self.borrow())
            .unwrap();

        if no_new_clone {
            return Ok(new_label.clone_index().unwrap());
        }

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

        let new_clone = builder.add_vertex(new_label);

        builder.add_edge(new_index, new_clone, new_label)?;

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

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

        Ok(new_clone)
    }
}

impl<T: GraphLabel> PartialEq for DefaultForest<ForestLabel<T>> {
    fn eq(&self, other: &Self) -> bool {
        let self_root = self.root();
        let other_root = other.root();

        if (self_root.is_some() && other_root.is_none())
            || (self_root.is_none() && other_root.is_some())
        {
            return false;
        } else if self_root.is_none() && other_root.is_none() {
            return true;
        }

        // both roots are not empty

        let self_root = self_root.unwrap();
        let other_root = other_root.unwrap();

        self.is_prefix(self_root, other).unwrap_or(false)
            && other.is_prefix(other_root, self).unwrap_or(false)
    }
}

impl<T: GraphLabel> Eq for DefaultForest<ForestLabel<T>> {}

impl<T: GraphLabel> DefaultForest<ForestLabel<T>> {
    /// A convenient helper function to plant a fragment under a
    /// node, if it has not been planted yet.
    ///
    /// To be precise, this function first checks if the node is
    /// packed; if so, then it checks every of the cloned children, to
    /// see if the fragment has already been planted.  If none of the
    /// clones have the fragment as a prefix, we make a new clone and
    /// plant the fragment there.
    ///
    /// On the other hand, if the node is a plain node, then it checks
    /// if the fragment is a prefix of the node.  If so, do nothing,
    /// else clone the node and plant the fragment there, unless the
    /// node has no children yet, in which case just plant the node
    /// there.
    ///
    /// A special case occurs when the node is the root node, in which
    /// case we clone it only when its degree is larger than one.
    ///
    /// Return either the original node or the cloned node at the end.
    pub(crate) fn plant_at_start(
        &mut self,
        node: usize,
        mut fragment: Self,
    ) -> Result<usize, Error> {
        if fragment.is_empty() {
            return Ok(node);
        }

        fragment.set_root(1)?;

        let node_label = self.vertex_label(node)?.ok_or(Error::NodeNoLabel(node))?;

        if node_label.is_packed() || node_label.clone_index().is_some() {
            let mut planted = false;

            let mut to_plant: Option<usize> = None;

            let mut node = node;

            if node_label.clone_index().is_some() {
                let mut parents = self.parents_of(node)?;

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

                node = parents.next().unwrap().node();
            }

            for clone in self.children_of(node)? {
                node = clone;

                if !self.is_empty_node(clone)? {
                    let first_child = self.nth_child(clone, 0)?;

                    if self.is_prefix(first_child, &fragment)? {
                        planted = true;

                        break;
                    }
                } else if to_plant.is_none() {
                    to_plant = Some(clone);
                }
            }

            if !planted {
                let clone = if let Some(cloned_node) = to_plant {
                    cloned_node
                } else {
                    self.clone_node(node, 0, false)?
                };

                self.plant(clone, fragment, false)?;

                return Ok(clone);
            }
        } else {
            let clone_threshold = if self.root == Some(node) { 1 } else { 0 };

            let satisfy_threshold = self.degree(node)? > clone_threshold;

            if !satisfy_threshold {
                self.plant(node, fragment, false)?;

                return Ok(node);
            }

            let first_child = self.nth_child(node, clone_threshold)?;

            let planted = self.is_prefix(first_child, &fragment)?;

            if !planted {
                let clone = self.clone_node(node, 0, false)?;

                self.plant(clone, fragment, false)?;

                return Ok(clone);
            }
        }

        Ok(node)
    }
}

pub mod splone;

pub mod extract;

impl<T: GraphLabel> DefaultForest<T> {
    /// Create a forest with only one leaf from a raw label, unlike
    /// `new_leaf`, which transforms the label for convenience.
    pub fn new_leaf_raw(label: T) -> Self {
        let mut graph = PLGraph::default();

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

        let root = Some(builder.add_vertex(label));

        Self { graph, root }
    }

    /// Set the root to the given node.
    pub fn set_root(&mut self, root: usize) -> Result<(), Error> {
        if root >= self.nodes_len() {
            return Err(Error::IndexOutOfBounds(root, self.nodes_len()));
        }

        self.root = Some(root);

        Ok(())
    }
}

impl DefaultForest<ForestLabel<GrammarLabel>> {
    /// Prints the forest without nodes that do not have ending
    /// positions.
    ///
    /// Nodes without ending positions are "unclosed nodes" that only
    /// serve the role of creating nodes with ending positions.
    pub fn print_closed_viz(&self, filename: &str) -> Result<(), std::io::Error> {
        let discard_nodes: std::collections::HashSet<_> = self
            .nodes()
            .filter(|node| match self.vertex_label(*node) {
                Ok(label) => {
                    if let Some(label) = label {
                        label.label().end().is_none()
                            || (matches!(self.degree(*node), Ok(0))
                                && matches!(self.parents_of(*node).map(|iter| iter.len()), Ok(0)))
                    } else {
                        true
                    }
                }
                Err(_) => true,
            })
            .collect();

        let filename = format!("output/{filename}");

        let preamble = "digraph nfa {
    fontname=\"Helvetica,Arial,sans-serif\"
    node [fontname=\"Helvetica,Arial,sans-serif\"]
    edge [fontname=\"Helvetica,Arial,sans-serif\"]
    rankdir=LR;\n";

        let mut post = String::new();

        for node in self.nodes() {
            if discard_nodes.contains(&node) {
                continue;
            }

            post.push_str(&format!(
                "    {node} [label = \"{}\"]\n",
                match self.vertex_label(node) {
                    Ok(Some(label)) => {
                        format!("{label}")
                    }
                    _ => {
                        " ε ".to_owned()
                    }
                }
            ));
        }

        for (source, target) in self.edges() {
            if discard_nodes.contains(&source) || discard_nodes.contains(&target) {
                continue;
            }

            post.push_str(&format!("    {source} -> {target}\n"));
        }

        post.push_str("}\n");

        let result = format!("{preamble}{post}");

        if std::fs::metadata(&filename).is_ok() {
            std::fs::remove_file(&filename)?;
        }

        let mut file = std::fs::File::options()
            .write(true)
            .create(true)
            .open(&filename)?;

        use std::io::Write;

        file.write_all(result.as_bytes())
    }

    /// Remove a node by removing all edges connecting with it.
    pub fn remove_node(&mut self, node_id: usize) -> Result<(), Error> {
        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

        let mut to_remove =
            Vec::with_capacity(builder.degree(node_id)? + builder.parents_of(node_id)?.len());

        to_remove.extend(
            builder
                .children_of(node_id)?
                .map(|target| (node_id, target)),
        );

        to_remove.extend(
            builder
                .parents_of(node_id)?
                .map(|parent| (parent.node(), node_id)),
        );

        for (source, target) in to_remove {
            builder.remove_edge(source, target, |_| true)?;
        }

        Ok(())
    }

    /// Set the position of every node.
    ///
    /// If ALLP is non-nil or if the node is a terminal node, also set
    /// the ending position whereever reasonable.
    pub(crate) fn set_pos(
        &mut self,
        atom: &DefaultAtom,
        pos: usize,
        allp: bool,
    ) -> Result<(), Error> {
        let mut builder = PLGBuilderMut::from_graph_mut(&mut self.graph);

        let nodes_len = builder.nodes_len();

        if !allp {
            for node in 0..nodes_len {
                let label = builder
                    .vertex_label(node)?
                    .ok_or(Error::NodeNoLabel(node))?;

                let mut label_label = label.label();

                label_label.set_start(pos);

                let new_label = ForestLabel::new(label_label, label.status);

                builder.set_label(node, new_label)?;
            }

            return Ok(());
        }

        // We assign every node to be open first, and then start from
        // any terminal node and assign them to be closed, then their
        // parents are rules.  If those rules are accepting, we assign
        // the rules and the parents of rules to be closed, and so on
        // and so forth.
        //
        // We need to test this behaviour, though.

        let mut closed_nodes: Vec<bool> = std::iter::repeat(false).take(nodes_len).collect();

        let mut closed_stack: Vec<usize> = Vec::with_capacity(nodes_len);

        for (node, closed_nodes_ptr) in (0..nodes_len).zip(closed_nodes.iter_mut()) {
            let label = builder
                .vertex_label(node)?
                .ok_or(Error::NodeNoLabel(node))?;

            if matches!(label.label().label().tnt(), Some(TNT::Ter(_))) {
                *closed_nodes_ptr = true;
                closed_stack.push(node);
            }
        }

        while let Some(node) = closed_stack.pop() {
            for parent in builder.parents_of(node)?.map(|p| p.node()) {
                *closed_nodes
                    .get_mut(parent)
                    .ok_or(Error::IndexOutOfBounds(parent, nodes_len))? = true;

                let label = builder
                    .vertex_label(parent)?
                    .ok_or(Error::NodeNoLabel(parent))?;

                if let Some(rule) = label.label().label().rule() {
                    if atom
                        .is_accepting(2 * rule + 1)
                        .map_err(|_| Error::IndexOutOfBounds(2 * rule + 1, atom.accepting_len()))?
                    {
                        closed_stack.push(parent);
                    }
                } else {
                    closed_stack.push(parent);
                }
            }
        }

        for (node, closed_p) in (0..nodes_len).zip(closed_nodes.iter().copied()) {
            let label = builder
                .vertex_label(node)?
                .ok_or(Error::NodeNoLabel(node))?;

            let mut label_label = label.label();

            label_label.set_start(pos);

            if closed_p {
                label_label.set_end(pos + 1);
            }

            let new_label = ForestLabel::new(label_label, label.status);

            builder.set_label(node, new_label)?;
        }

        Ok(())
    }
}

/// Print the labels found in the forest, so that we can easily
/// understand what those labels mean.
pub fn print_labels(
    atom: impl Borrow<DefaultAtom>,
    forest: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
) -> Result<(), Box<dyn std::error::Error>> {
    let forest = forest.borrow();
    let atom = atom.borrow();

    for node in forest.nodes() {
        let label = forest.vertex_label(node)?;

        if let Some(label) = label {
            let label = label.label.label();

            match label {
                GrammarLabelType::TNT(tnt) => {
                    println!("{tnt} = {}", atom.name_of_tnt(tnt)?);
                }
                GrammarLabelType::Rule(pos) => {
                    println!("pos {pos} = {}", atom.rule_pos_string(pos)?);
                }
            }
        } else {
            return Err(Error::NodeNoLabel(node).into());
        }
    }

    Ok(())
}

#[allow(unused_macros)]
macro_rules! leaf (
    ($label:expr, $type:tt) =>{
        DefaultForest::<ForestLabel<$type>>::new_leaf($label)
    };
    ($label:expr) => {
        DefaultForest::<ForestLabel<usize>>::new_leaf($label)
    }
);

#[allow(unused_imports)]
pub(crate) use leaf;

#[cfg(test)]
mod item_test {
    use super::*;
    use graph::Graph;

    fn make_forest_1() -> Result<DefaultForest<ForestLabel<usize>>, Box<dyn std::error::Error>> {
        let mut result = leaf!(0);

        for i in 1..5 {
            result.plant(0, leaf!(i), false)?;
        }

        for i in 5..10 {
            result.plant(2, leaf!(i), false)?;
        }

        result.plant(4, leaf!(10), false)?;
        result.plant(4, leaf!(11), false)?;

        let clone = result.clone_node(4, 1, false)?;

        result.plant(clone, leaf!(12), false)?;

        Ok(result)
    }

    #[test]
    fn test_forest_api() -> Result<(), Box<dyn std::error::Error>> {
        let forest: DefaultForest<ForestLabel<usize>> = Default::default();

        // empty forest

        assert!(forest.is_empty());

        // leaf forest

        let mut forest = leaf!(0, usize);

        assert_eq!(forest.nodes_len(), 1);
        assert_eq!(forest.root(), Some(0));

        // add some child

        forest.plant(0, leaf!(1), false)?;

        assert_eq!(forest.nodes_len(), 2);
        let mut children = forest.children_of(0)?;
        assert_eq!(children.next(), Some(1));
        assert_eq!(children.next(), None);

        // add more children

        forest.plant(0, leaf!(2), false)?;
        forest.plant(0, leaf!(3), false)?;
        forest.plant(0, leaf!(4), false)?;
        forest.plant(2, leaf!(5), false)?;

        assert_eq!(forest.nodes_len(), 6);
        let mut children = forest.children_of(0)?;
        assert_eq!(children.next(), Some(1));
        assert_eq!(children.next(), Some(2));
        assert_eq!(children.next(), Some(3));
        assert_eq!(children.next(), Some(4));
        let mut children = forest.children_of(2)?;
        assert_eq!(children.next(), Some(5));
        assert_eq!(children.next(), None);

        let mut test_forest = leaf!(0);
        test_forest.plant(0, leaf!(1), false)?;
        test_forest.plant(0, leaf!(2), false)?;
        test_forest.plant(0, leaf!(3), false)?;
        test_forest.plant(2, leaf!(5), false)?;

        assert!(forest.is_prefix(0, &test_forest)?);

        let mut test_forest = leaf!(0);
        test_forest.plant(0, leaf!(1), false)?;
        test_forest.plant(0, leaf!(2), false)?;
        // this child of the root should have label 3 in order to be a
        // prefix.
        test_forest.plant(0, leaf!(4), false)?;
        test_forest.plant(2, leaf!(5), false)?;

        assert!(!forest.is_prefix(0, &test_forest)?);

        let mut test_forest = leaf!(2);
        test_forest.plant(0, leaf!(5), false)?;

        assert!(forest.is_prefix(2, &test_forest)?);
        assert!(!forest.is_prefix(0, &test_forest)?);

        // now test cloning

        // add a duplicate label
        forest.plant(3, leaf!(5), false)?;

        assert_eq!(forest.nodes_len(), 6);

        // add two children to 5

        forest.plant(5, leaf!(6), false)?;
        forest.plant(5, leaf!(7), false)?;

        // clone and preserve one child
        let cloned = forest.clone_node(5, 1, false)?;

        assert_eq!(forest.nodes_len(), 10);

        assert_eq!(forest.degree(cloned)?, 1);
        assert_eq!(forest.degree(5)?, 2);

        #[cfg(feature = "test-print-viz")]
        forest.print_viz("forest.gv")?;

        Ok(())
    }

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

        let mut test_forest = leaf!(0);
        test_forest.plant(0, leaf!(13), false)?;

        assert_eq!(forest.is_prefix(0, &test_forest), Ok(false));

        forest.plant(0, leaf!(13), false)?;

        assert_eq!(forest.degree(0), Ok(5));

        Ok(())
    }

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

        let mut test_forest = leaf!(0);
        test_forest.plant(0, leaf!(9), false)?;

        assert_eq!(forest.is_prefix(0, test_forest), Ok(false));

        forest.plant(0, leaf!(9), false)?;

        assert_eq!(forest.degree(0), Ok(5));

        assert_eq!(forest.children_of(0)?.nth(4), Some(9));

        Ok(())
    }

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

        let mut test_forest = leaf!(2);

        test_forest.plant(0, leaf!(5), false)?;

        let clone = test_forest.clone_node(0, 0, false)?;

        test_forest.plant(clone, leaf!(6), false)?;

        assert_eq!(forest.is_prefix(0, &test_forest), Ok(false));

        let mut answer = forest.clone();

        forest.plant(0, test_forest, false)?;

        let clone = answer.clone_node(2, 0, false)?;

        answer.plant(clone, leaf!(6), false)?;

        assert_eq!(forest, answer);

        Ok(())
    }

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

        let mut test_forest = leaf!(4);

        test_forest.plant(0, leaf!(10), false)?;
        test_forest.plant(0, leaf!(12), false)?;

        assert_eq!(forest.is_prefix(12, &test_forest), Ok(true));

        let answer = forest.clone();

        forest.plant(0, test_forest, false)?;

        assert_eq!(forest, answer);

        let mut test_forest = leaf!(4);

        test_forest.plant(0, leaf!(10), false)?;
        test_forest.plant(0, leaf!(9), false)?;

        assert_eq!(forest.is_prefix(12, &test_forest), Ok(false));

        let mut answer = forest.clone();

        forest.plant(0, test_forest, false)?;

        let clone = answer.clone_node(4, 1, false)?;

        answer.plant(clone, leaf!(9), false)?;

        assert_eq!(forest, answer);

        Ok(())
    }

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

        let mut test_forest = leaf!(4);

        test_forest.plant(0, leaf!(10), false)?;
        test_forest.plant(0, leaf!(12), false)?;

        let clone = test_forest.clone_node(0, 1, false)?;

        test_forest.plant(clone, leaf!(9), false)?;

        assert_eq!(forest.is_prefix(12, &test_forest), Ok(false));

        let mut answer = forest.clone();

        forest.plant(0, test_forest, false)?;

        let clone = answer.clone_node(4, 1, false)?;

        answer.plant(clone, leaf!(9), false)?;

        assert_eq!(forest, answer);

        Ok(())
    }

    #[test]
    fn test_eq() -> Result<(), Box<dyn std::error::Error>> {
        let mut forest = leaf!(0, usize);

        forest.plant(0, leaf!(1), false)?;
        forest.plant(0, leaf!(2), false)?;
        forest.plant(0, leaf!(3), false)?;
        forest.plant(0, leaf!(4), false)?;
        forest.plant(2, leaf!(5), false)?;

        let mut test_forest = leaf!(0);
        test_forest.plant(0, leaf!(1), false)?;
        test_forest.plant(0, leaf!(2), false)?;
        test_forest.plant(0, leaf!(3), false)?;
        test_forest.plant(2, leaf!(5), false)?;

        assert_ne!(forest, test_forest);
        assert_ne!(test_forest, forest);

        test_forest.plant(0, leaf!(4), false)?;

        assert_eq!(forest, test_forest);
        assert_eq!(test_forest, forest);

        Ok(())
    }
}