path: root/chain/src/item/genins.rs

//! This module implements the generation and insertion of item
//! derivation forests.
//!
//! This is used for the chain-rule machine to conveniently produce
//! item derivations into a forest.  This forest can serve as a rough
//! approximation of the parse forests, and can be executed in other
//! semirings later on.

use super::*;
use crate::{atom::DefaultAtom, default::Error, item::default::DefaultForest, Edge};
use grammar::{Error as GrammarError, GrammarLabel, GrammarLabelType, TNT};
use graph::Graph;

use core::borrow::Borrow;
use std::collections::HashSet as Set;

/// A helper function to generate a fragment of forest.
///
/// It simply constructs a root node and then appends
/// successive nodes as successive children of the previous
/// node.  Also the starting positions will all be set to the
/// same position.
///
/// If the input is empty, this returns an empty forest;
/// otherwise the result is not empty.
pub fn generate_fragment(
    labels: impl AsRef<[GrammarLabelType]>,
    pos: usize,
) -> Result<DefaultForest<ForestLabel<GrammarLabel>>, crate::default::Error> {
    let mut labels_iter = labels.as_ref().iter();
    let mut result: DefaultForest<ForestLabel<GrammarLabel>>;

    if let Some(first_label) = labels_iter.next() {
        result = DefaultForest::new_leaf(GrammarLabel::new(*first_label, pos));

        let mut index = 0;

        for label in labels_iter {
            result.plant(
                index,
                DefaultForest::new_leaf(GrammarLabel::new(*label, pos)),
                false,
            )?;

            // To prevent duplication of labels causing
            // panics, we query the index of the new node.
            index = result
                .query_label(GrammarLabel::new(*label, pos).into())
                // REVIEW: Perhaps a LabelNoNode error?
                .ok_or(Error::Invalid)?;
        }
    } else {
        result = Default::default();
    }

    Ok(result)
}

impl DefaultForest<ForestLabel<GrammarLabel>> {
    /// Insert an item derivation forest into a recording forest.
    ///
    /// We need the help of other things just for finding the correct
    /// places to insert these item fragments.
    pub fn insert_item(
        &mut self,
        label: Edge,
        fragment: impl Borrow<DefaultForest<ForestLabel<GrammarLabel>>>,
        atom_child_iter: impl Iterator<Item = usize>,
        atom: &DefaultAtom,
    ) -> Result<PaSe, Error> {
        /// Convert an error telling us that an index is out of bounds.
        ///
        /// # Panics
        ///
        /// The function panics if the error is not of the expected
        /// kind.
        fn index_out_of_bounds_conversion(ge: GrammarError) -> Error {
            match ge {
                GrammarError::IndexOutOfBounds(index, bound) => {
                    Error::IndexOutOfBounds(index, bound)
                }
                _ => Error::Invalid,
            }
        }

        let fragment = fragment.borrow();

        let pase = label.forest_source();

        let parents: Vec<Parent> = {
            let mut result = Vec::new();

            if let Some(parent) = pase.parent() {
                result.push(parent);
            } else {
                let (root, leaf) = pase.segment().unwrap();
                let mut seen_nodes = Set::new();

                let mut stack = vec![root];

                while let Some(top) = stack.pop() {
                    if seen_nodes.contains(&top) {
                        continue;
                    }

                    seen_nodes.insert(top);

                    for (index, child) in self.children_of(top)?.enumerate() {
                        if child == leaf {
                            result.push(Parent::new(top, index));
                        } else {
                            stack.push(child);
                        }
                    }
                }
            }

            result
        };

        for atom_child in atom_child_iter {
            // Find reduction information.
            let reduction_info = atom
                .query_reduction(label.label(), atom_child)
                .map_err(index_out_of_bounds_conversion)?;

            let mut stack = parents.clone();
            let mut second_stack = Vec::new();

            // locate the nodes
            for reduction_nt in reduction_info.iter().copied().flatten().rev() {
                while let Some(node) = stack.pop() {
                    // REVIEW: A lot of labels appear here.
                    // Perhaps I need to refactor something?
                    if matches!(
                        self
                            .vertex_label(node.node())?
                            .ok_or_else(|| Error::NodeNoLabel(node.node()))?
                            .label()
                            .label(),
                        GrammarLabelType::TNT(TNT::Non(nt)) if nt == *reduction_nt
                    ) {
                        for parent in self.parents_of(node.node())? {
                            debug_assert!(matches!(
                                    self.vertex_label(parent.node()),
                                    Ok(Some(label)) if
                                        label
                                        .label()
                                        .label()
                                        .rule()
                                        .is_some()));

                            second_stack.extend(self.parents_of(parent.node())?.filter(|n| {
                                matches!(self.vertex_label(n.node()),
                                                 Ok(Some(label))
                                                 if matches!(
                                                     label.label().label().tnt(),
                                                     Some(TNT::Non(_))))
                            }));
                        }
                    }
                }

                std::mem::swap(&mut stack, &mut second_stack);

                if stack.is_empty() {
                    break;
                }
            }

            if stack.is_empty() {
                return Err(Error::CannotPlant);
            }

            for parent in stack.into_iter() {
                if parent.edge() + 1 >= self.degree(parent.node())? {
                    self.plant(parent.node(), fragment, false)?;
                } else {
                    let nth_child = self.nth_child(parent.node(), parent.edge() + 1)?;

                    if self.is_prefix(nth_child, fragment)? {
                        // do nothing
                        continue;
                    }

                    let cloned_node = self.clone_node(nth_child)?;

                    self.plant(cloned_node, fragment, false)?;
                }
            }
        }

        let result = if fragment.nodes_len() == 2 {
            let root_label = fragment.vertex_label(0)?.unwrap();
            let leaf_label = fragment.vertex_label(1)?.unwrap();

            // it has been planted, so should be safe.
            let node = self.query_label(root_label).unwrap();

            let edge = {
                let mut result = None;

                for (index, child) in self.children_of(node)?.enumerate() {
                    if matches!(self.vertex_label(child)?, Some(child_label) if child_label == leaf_label)
                    {
                        result = Some(index);
                        break;
                    }
                }

                if let Some(result) = result {
                    result
                } else {
                    unreachable!("the forest is wrongly planted");
                }
            };

            PaSe::Parent(node, edge)
        } else {
            let root_label = fragment.vertex_label(0)?.unwrap();
            let leaf_label = fragment.vertex_label(fragment.nodes_len() - 1)?.unwrap();

            PaSe::Segment(
                self.query_label(root_label).unwrap(),
                self.query_label(leaf_label).unwrap(),
            )
        };

        Ok(result)
    }
}