path: root/forest/src/iter/query/matching.rs

//! This file defines some traits and basic implementations for
//! matching pattern vertices against target vertices.

use crate::{bytes::BytesForest, ForestLabel};

#[allow(unused_imports)]
use graph::{
    error::Error as GError, ELabelGraph, Graph, GraphLabel, LabelGraph, PLGraph, SLGBuilder,
    SLGraph, VLabelGraph,
};

use graph_macro::Graph;

use grammar::GrammarLabel;

/// An aggregate struct that holds information about a parent as well
/// as its vertex label and the corresponding edge label.
#[derive(Debug, Clone, Copy)]
pub struct EVLabelParent<T: GraphLabel> {
    parent: usize,
    // edge_index: usize,
    parent_label: T,
    edge_label: EdgeType,
}

impl<T: GraphLabel> EVLabelParent<T> {
    /// Construct a new instance.
    pub fn new(parent: usize, parent_label: T, edge_label: EdgeType) -> Self {
        Self {
            parent,
            parent_label,
            edge_label,
        }
    }

    /// Retrieve the `parent` field.
    pub fn parent(&self) -> usize {
        self.parent
    }

    // /// Retrieve the `edge_index` field.
    // pub fn edge_index(&self) -> usize {
    //     self.edge_index
    // }

    /// Retrieve the `parent_label` field.
    pub fn parent_label(&self) -> T {
        self.parent_label
    }

    /// Retrieve the `edge_label` field.
    pub fn edge_label(&self) -> EdgeType {
        self.edge_label
    }
}

/// A trait for pattern graphs.
pub trait Pattern<T: GraphLabel>: VLabelGraph<T> + ELabelGraph<EdgeType> {
    /// An iterator delegation for parents and vertex and edge labels.
    type ParentIter<'a>: Iterator<Item = EVLabelParent<T>> + 'a
    where
        Self: 'a,
        T: 'a;

    /// Return an iterator that goes through the parents and edge
    /// labels.
    fn parents(&self, node: usize) -> Result<Self::ParentIter<'_>, GError>;
}

/// A trait for target graphs.
pub trait Target<T: GraphLabel>: VLabelGraph<T> {
    /// Return an array of node indices whose labels match the given
    /// label.
    fn filter_label(&self, label: T) -> Box<[usize]> {
        let _label = label;

        (0..self.nodes_len()).collect::<Vec<_>>().into_boxed_slice()
    }
}

/// A custom pattern type with a fixed edge label and a generic vertex
/// label.
///
/// This type contains two graphs, with the extra one containing
/// parentship information.
#[derive(Debug, Clone, Graph)]
pub struct SimplePattern<T: GraphLabel> {
    graph: SLGBuilder<T, EdgeType>,
    parents_graph: SLGBuilder<T, EdgeType>,
}

impl<T: GraphLabel> Default for SimplePattern<T> {
    fn default() -> Self {
        let graph = SLGBuilder::default();
        let parents_graph = SLGBuilder::default();
        Self {
            graph,
            parents_graph,
        }
    }
}

impl<T: GraphLabel> SimplePattern<T> {
    /// Return a new pattern from an underlying graph builder.
    pub fn new(graph: SLGBuilder<T, EdgeType>) -> Result<Self, GError> {
        let nodes_len = graph.nodes_len();

        let mut parents_graph: SLGBuilder<T, EdgeType> = SLGBuilder::with_capacity(nodes_len);

        for node in 0..nodes_len {
            // Nodes must have labels.
            let label = VLabelGraph::vertex_label(&graph, node)?.unwrap();

            parents_graph.add_vertex(label);
        }

        for node in 0..nodes_len {
            for (label, child) in ELabelGraph::edlabren_of(&graph, node)? {
                parents_graph.add_edge(node, child, label)?;
            }
        }

        Ok(Self {
            graph,
            parents_graph,
        })
    }
}

impl<T: GraphLabel> VLabelGraph<T> for SimplePattern<T> {
    type TupleIter<'a> = <SLGBuilder::<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>
    where
        Self: 'a,
        T: 'a;

    fn verlabren_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
        self.graph.verlabren_of(node_id)
    }
}

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

    type TupleIter<'a> = <SLGBuilder::<T, EdgeType> as LabelGraph<EdgeType>>::TupleIter<'a>
    where
        Self: 'a,
        T: 'a;

    type LabelIter<'a>  = std::iter::Empty<(&'a EdgeType, std::iter::Empty<usize>)>
    where
        Self: 'a,
        T: 'a;

    type EdgeLabelIter<'a> = std::option::IntoIter<EdgeType>
    where
        Self: 'a,
        T: 'a;

    fn edge_label(&self, source: usize, target: usize) -> Result<Self::EdgeLabelIter<'_>, GError> {
        LabelGraph::edge_label(&self.graph, source, target)
    }

    fn find_children_with_label(
        &self,
        node_id: usize,
        label: &EdgeType,
    ) -> Result<<Self as LabelGraph<EdgeType>>::Iter<'_>, GError> {
        self.graph.find_children_with_label(node_id, label)
    }

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

    fn tuples_of(&self, node_id: usize) -> Result<Self::TupleIter<'_>, GError> {
        self.graph.tuples_of(node_id)
    }

    fn has_edge_label(
        &self,
        node_id: usize,
        label: &EdgeType,
        target: usize,
    ) -> Result<bool, GError> {
        self.graph.has_edge_label(node_id, label, target)
    }
}

/// Iterator delegator for parents.
#[derive(Debug, Clone)]
pub struct PatternParents<'a, T>
where
    T: GraphLabel + 'a,
{
    vertex_iter: <SLGBuilder<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>,
    edge_iter: <SLGBuilder<T, EdgeType> as ELabelGraph<EdgeType>>::TupleIter<'a>,
}

impl<'a, T> PatternParents<'a, T>
where
    T: GraphLabel + 'a,
{
    /// Construct a new iterator.
    pub fn new(
        vertex_iter: <SLGBuilder<T, EdgeType> as VLabelGraph<T>>::TupleIter<'a>,
        edge_iter: <SLGBuilder<T, EdgeType> as ELabelGraph<EdgeType>>::TupleIter<'a>,
    ) -> Self {
        Self {
            vertex_iter,
            edge_iter,
        }
    }
}

impl<'a, T: 'a + GraphLabel> Iterator for PatternParents<'a, T> {
    type Item = EVLabelParent<T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.vertex_iter.next().and_then(|(vlabel, target)| {
            self.edge_iter
                .next()
                .map(|(elabel, _)| EVLabelParent::new(target, vlabel, elabel))
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.vertex_iter.size_hint()
    }
}

impl<'a, T: 'a + GraphLabel> ExactSizeIterator for PatternParents<'a, T> {
    #[inline]
    fn len(&self) -> usize {
        self.vertex_iter.len()
    }
}

impl<T: GraphLabel> Pattern<T> for SimplePattern<T> {
    type ParentIter<'a> = PatternParents<'a, T> where T:'a;

    fn parents(&self, node: usize) -> Result<Self::ParentIter<'_>, GError> {
        let vertex_iter = self.parents_graph.verlabren_of(node)?;
        let edge_iter = self.parents_graph.edlabren_of(node)?;

        Ok(PatternParents::new(vertex_iter, edge_iter))
    }
}

// Implement Target for three types.  Another type "DefaultForest"
// should implement this trait on its own when the need arises.
//
// Note that SimplePattern also implements the Target trait.

impl<T: GraphLabel> Target<T> for SimplePattern<T> {
    fn filter_label(&self, label: T) -> Box<[usize]> {
        (0..self.nodes_len())
            .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label)))
            .collect::<Vec<_>>()
            .into_boxed_slice()
    }
}

impl<T: GraphLabel> Target<T> for PLGraph<T> {
    fn filter_label(&self, label: T) -> Box<[usize]> {
        (0..self.nodes_len())
            .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label)))
            .collect::<Vec<_>>()
            .into_boxed_slice()
    }
}

impl Target<ForestLabel<GrammarLabel>> for BytesForest {
    fn filter_label(&self, label: ForestLabel<GrammarLabel>) -> Box<[usize]> {
        (0..self.nodes_len())
            .filter(|node| VLabelGraph::vertex_label(self, *node) == Ok(Some(label)))
            .collect::<Vec<_>>()
            .into_boxed_slice()
    }
}

// Edge-filtering types

/// The type of edges that this edge can match against.
///
/// For the time being, we can only match either a direct child
/// (i.e. no extra condition) or a sibling of another node.
///
/// In the future, we shall be able to use supplemental graphs to
/// match edges.
///
/// This can be used as [`Graphlabel`][graph::GraphLabel].
#[derive(Copy, Clone, Debug, Default, Eq, PartialEq, Hash, Ord, PartialOrd)]
pub enum EdgeType {
    /// Matches a direct child.
    #[default]
    Direct,
    /// Match a sibling of another node.
    Sibling(usize),
}

impl std::fmt::Display for EdgeType {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            EdgeType::Direct => write!(f, "direct edge"),
            EdgeType::Sibling(node) => write!(f, "sibling of {node}"),
        }
    }
}

impl EdgeType {
    /// Return a Sibling-type edge.
    pub fn sibling(node: usize) -> Self {
        Self::Sibling(node)
    }

    /// Return whether this edge matches.
    pub fn matches<G: Graph>(&self, g: &G, from: usize, to: usize) -> Result<bool, GError> {
        match self {
            EdgeType::Direct => g.has_edge(from, to),
            EdgeType::Sibling(sibling) => {
                let mut iter = g.children_of(from)?;

                while let Some(child) = iter.next() {
                    if child == *sibling {
                        return Ok(iter.next() == Some(to));
                    }
                }

                // sibling not found

                Ok(false)
            }
        }
    }
}