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

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.
    ///
    /// # 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.
    fn splone(&mut self, node: usize, end: Option<usize>, edge_index: usize) -> Result<(), 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() {
            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(());
            }

            dbg!();
            self.clone_node(node, edge_index + 1, false)?;

            return Ok(());
        }

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

        let new_label = if let Some(label) = new_label {
            label
        } else {
            return Ok(());
        };

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

        // replace the label directly

        // if new_label.clone_index().is_none() {
        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();

            assert!(get_rule_label(parent_label).is_some());
            assert_eq!(builder.degree(parent)?, 1);

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

            let parent_label = ForestLabel::from(parent_label);

            builder.set_label(parent, parent_label)?;
        }
        // } else {
        //     // REVIEW: Call `split_node` in this situation as well?

        //     // If we are here, the new label should have a packed
        //     // parent.
        //     let packed = self
        //         .query_label(ForestLabel::new(new_label.label(), ForestLabelType::Packed))
        //         .unwrap();

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

        //     builder.set_label(node, new_label)?;

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

        //     for parent in parents.iter() {
        //         builder.redirect(parent.node(), parent.edge(), packed)?;
        //     }

        //     builder.add_edge(packed, node, new_label)?;
        // }

        Ok(())
    }

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

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

        let mut new_node = builder.add_vertex(new_label);

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

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

            Some(packed)
        } else {
            None
        };

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

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

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

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

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

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

                assert!(get_rule_label(parent_label).is_some());
                assert_eq!(self.degree(parent.node())?, 1);

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

                let parent_label = ForestLabel::from(parent_label);

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

                let new_parent = builder.add_vertex(parent_label);

                if let Some(packed) = new_packed {
                    new_node = packed;
                }

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

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

            result
        };

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

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

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

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

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

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

        Ok(())
    }

    /// Procedure for the new label:
    ///
    /// 1. Copy the old label.
    ///
    /// 2. Set the end to `pos`.
    ///
    /// 3. Pack the label.
    ///
    /// 4. Check if this label already exists.  If so, clone the label and
    /// return it.
    ///
    /// 5. Else set the label to be a plain label.
    ///
    /// 6. Check if this plain label already exists.  If so, clone the
    /// existing label, and return the clone of the cloned label.
    ///
    /// 7. Else return the plain label.
    fn create_new_label(
        &mut self,
        node: usize,
        end: Option<usize>,
        edge_index: usize,
    ) -> Result<Option<ForestLabel<GrammarLabel>>, Error> {
        let mut copied_label = self
            .vertex_label(node)?
            .ok_or(Error::NodeNoLabel(node))?
            .label();

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

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

        if let Some(packed) = self.query_label(label) {
            for child in self.children_of(packed)? {
                if self.has_same_children(child, node, self.degree(child)?, edge_index + 1)? {
                    return Ok(None);
                }
            }

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

            Ok(Some(ForestLabel::new(
                copied_label,
                ForestLabelType::Cloned(clone_index),
            )))
        } else {
            let plain_label = ForestLabel::new(copied_label, ForestLabelType::Plain);

            if let Some(existing) = self.query_label(plain_label) {
                if self.has_same_children(existing, node, self.degree(existing)?, edge_index + 1)? {
                    return Ok(None);
                }

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

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

    /// 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, except at a given index, where it points to
    /// another given node.
    fn has_same_children_but_one(
        &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 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).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).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(7, 1, 3), GrammarLabel),
            false,
        )?;

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

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

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

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

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

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

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

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

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

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

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

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

        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)?;
        test_forest.splone(15, Some(3), 0)?;

        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)?;
        test_forest.splone(15, Some(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!(
                "repeated splone(17, Some(3), 0) - splone(15, Some(3), 0) produced wrong forest"
            );
        }

        Ok(())
    }
}