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

#![warn(missing_docs)]
//! This module implements the type of items for the chain-rule
//! machine.
//!
//! More specifically, it implements the iten derivation forests for
//! the machine.

use graph::{error::Error as GError, GraphLabel, LabelGraph, Parent, ParentsGraph};

use std::borrow::Borrow;

/// A parent or a virtual segment.
///
/// # Parent
///
/// A parent is a node with an edge index, which represents a certain
/// edge.
///
/// # Virtual Segment
///
/// A virtual segment represents an expansion from a non-terminal by a
/// terminal.  We do not directly add this segment when we encounter
/// this expansion at the start because this expansion might contain
/// multiple derivations some of which might not be used.
///
/// If we add the expansion immediately when we encounter it, we have
/// to later discern and delete those unwanted derivations.  This is
/// asking for trouble, as I learned from experiences.
///
/// # Empty
///
/// Also this might be empty if it represents the root node.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
pub enum PaVi {
    /// An edge from a node, as the n-th child, along with the
    /// nth-child node number.
    Parent(usize, usize, usize),
    /// A virtual segment from a non-terminal by a terminal, rooted at
    /// a node.
    ///
    /// # Tuple elements
    ///
    /// The contained tuple is of the form `(nt, t, node)` , which
    /// means a virtually added node at the `node` representing the
    /// expansion from the non-terminal `nt` by the terminal `t`.
    Virtual(usize, usize, usize),
    /// This is an empty segment that represents the root node.  This
    /// is a special case for the unit state of the chain-rule
    /// machine.
    #[default]
    Empty,
}

impl std::fmt::Display for PaVi {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Parent(node, edge, child) => {
                write!(f, "the {edge}-th edge from {node} to {child}")
            }
            Self::Virtual(nt, t, node) => write!(
                f,
                "a virtual node for non-terminal {nt} and terminal {t} at node {node}"
            ),
            Self::Empty => write!(f, "empty segment at root"),
        }
    }
}

impl PaVi {
    /// Get the Parent variant.
    fn parent(self) -> Option<Parent> {
        if let Self::Parent(node, edge, _) = self {
            Some(Parent::new(node, edge))
        } else {
            None
        }
    }

    fn is_virtual(self) -> bool {
        matches!(self, Self::Virtual(_, _, _))
    }

    /// Is this an empty segment?
    fn is_empty(self) -> bool {
        self == Self::Empty
    }
}

/// An internal type that indicates the status of a node as either a
/// packed, cloned, or plain node.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Default)]
pub enum ForestLabelType {
    /// A packed node
    Packed,
    /// A plain node
    #[default]
    Plain,
    /// A cloned node
    Cloned(usize),
}

impl std::fmt::Display for ForestLabelType {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        match self {
            Self::Packed => write!(f, "packed"),
            Self::Plain => write!(f, "plain"),
            Self::Cloned(index) => write!(f, "clone({index})"),
        }
    }
}

/// A type that encodes the properties demanded by a forest.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
pub struct ForestLabel<T: GraphLabel> {
    label: T,
    status: ForestLabelType,
}

impl<T: GraphLabel> std::fmt::Display for ForestLabel<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if !matches!(self.status, ForestLabelType::Plain) {
            write!(f, "{}, {}", self.label, self.status)
        } else {
            write!(f, "{}", self.label)
        }
    }
}

/// The type of erros for converting forest labels.
#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub enum ForestLabelError {
    /// Try to pack a cloned node.
    PackClone,
    /// Try to clone a packed node.
    ClonePack,
}

impl std::fmt::Display for ForestLabelError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::PackClone => write!(f, "cannot pack a cloned node"),
            Self::ClonePack => write!(f, "cannot clone a packed node"),
        }
    }
}

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

impl<T: GraphLabel> ForestLabel<T> {
    /// Construct a new label with the inner `label` and `status`.
    pub fn new(label: T, status: ForestLabelType) -> Self {
        Self { label, status }
    }

    /// Retrieve the label.
    pub fn label(&self) -> T {
        self.label
    }

    /// Return true if and only if this node is packed.
    pub fn is_packed(&self) -> bool {
        self.status == ForestLabelType::Packed
    }

    /// Retrieve the optional clone index.
    pub fn clone_index(&self) -> Option<usize> {
        match self.status {
            ForestLabelType::Cloned(index) => Some(index),
            _ => None,
        }
    }

    /// Return true if and only if this node is a plain node.
    pub fn is_plain(&self) -> bool {
        self.status == ForestLabelType::Plain
    }

    /// Try to clone a node.
    pub fn clone<F>(self, forest: &F) -> Result<Self, ForestLabelError>
    where
        F: LabelGraph<ForestLabel<T>>,
    {
        if self.is_packed() {
            dbg!();
            Err(ForestLabelError::ClonePack)
        } else {
            let clone_index = if let Some(old_index) = self.clone_index() {
                let mut new_index: usize = old_index + 1;

                let mut new_label = Self {
                    status: ForestLabelType::Cloned(new_index),
                    ..self
                };

                while forest.query_label(new_label).is_some() {
                    new_index += 1;
                    new_label = Self {
                        status: ForestLabelType::Cloned(new_index),
                        ..self
                    };
                }

                new_index
            } else {
                0
            };

            Ok(Self {
                status: ForestLabelType::Cloned(clone_index),
                ..self
            })
        }
    }

    /// Try to pack a node.
    pub fn pack(self) -> Result<Self, ForestLabelError> {
        if self.clone_index().is_some() {
            Err(ForestLabelError::PackClone)
        } else {
            let new_label = Self {
                status: ForestLabelType::Packed,
                ..self
            };

            Ok(new_label)
        }
    }
}

impl<T: GraphLabel> From<T> for ForestLabel<T> {
    fn from(label: T) -> Self {
        let status = ForestLabelType::default();
        Self { label, status }
    }
}

// REVIEW: Should we move this trait (and only this trait) to a
// separate crate, or is it enough to keep it here?

/// The expected behaviours of an item derivation forest.
///
/// Note that it requires only a subset of the functionalities of
/// labelled graphs.
pub trait Forest<T: GraphLabel>: ParentsGraph + LabelGraph<ForestLabel<T>> {
    /// The type of errors for operations on the forest.
    type Error: std::error::Error + From<GError> + From<ForestLabelError>;

    /// Return the root of the forest.
    ///
    /// A forest without a root is regarded as empty.
    fn root(&self) -> Option<usize>;

    /// Construct a forest consisting of one leaf node with the given
    /// label.
    fn new_leaf(label: T) -> Self;

    /// Transform the label at the given node.
    fn transform_label(
        &mut self,
        node_id: usize,
        transform: impl FnOnce(T) -> T,
    ) -> Result<(), Self::Error>;

    /// Detect if the fragment is a prefix of the sub-forest rooted at
    /// `node_id`.
    fn is_prefix<F>(&self, node_id: usize, fragment: F) -> Result<bool, Self::Error>
    where
        F: Borrow<Self>;

    /// Extend the forest by adjoining another forest at a given node.
    fn plant<F>(&mut self, node_id: usize, fragment: F, planted: bool) -> Result<(), Self::Error>
    where
        F: Borrow<Self>;

    /// Clone a node by making a new node and making all the nodes
    /// that previously pointed to the old node now point to the new
    /// node, and the new node points to the old node.  Return the
    /// index of the new node.  However, if, and only if,
    /// `no_new_clone` is `true`, do not make a new clone; instead
    /// return the clone index that would be used if a new clone was
    /// made.
    ///
    /// Also, `preserved_edges_num` many edges out of the old node
    /// will be copied to be the children of the new node.
    ///
    /// The labels of the representing node and of the cloned node
    /// will be handled automatically.
    fn clone_node(
        &mut self,
        node_id: usize,
        preserved_edges_num: usize,
        no_new_clone: bool,
    ) -> Result<usize, Self::Error>;
}

pub mod default;

pub mod genins;

pub use genins::generate_fragment;

pub mod reduction;