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

//! This module implements an iterator of forests, which provides
//! querying capabilities.

use super::*;

use graph::{error::Error as GError, labelled::SLGraph, Graph};

use graph_macro::Graph;

/// The label of a query graph.
///
/// Such a label is responsible for matching forest labels.
pub trait QueryLabel: GraphLabel {
    /// The type of labels this matches against.
    type Obj: GraphLabel;

    /// Determine whether or not a label matches this query label.
    fn matches(&self, label: Self::Obj, status: ForestLabelType) -> bool {
        let _ = label;
        let _ = status;

        false
    }

    /// Perform the query for one single query label.
    fn run<F>(
        &self,
        forest: &F,
        node: usize,
        packs: &mut Vec<(usize, usize)>,
    ) -> Result<Option<usize>, QRError>
    where
        F: LabelGraph<ForestLabel<<Self as QueryLabel>::Obj>>,
    {
        let mut dfs_stack: Vec<usize> = vec![node];

        let nodes_len = forest.nodes_len();

        while let Some(node) = dfs_stack.pop() {
            let label = match forest.vertex_label(node) {
                Ok(None) => return Err(QRError::NodeNoLabel(node)),
                Err(_) => return Err(QRError::IndexOutOfBounds(node, nodes_len)),
                Ok(Some(label)) => label,
            };

            let status = label.status();
            let label = label.label();

            if status == ForestLabelType::Packed {
                packs.push((node, 0));

                dfs_stack.extend(forest.children_of(node).unwrap().take(1));

                continue;
            }

            if self.matches(label, status) {
                return Ok(Some(node));
            }

            dfs_stack.extend(
                forest
                    .children_of(node)
                    .unwrap()
                    .collect::<Vec<_>>()
                    .into_iter()
                    .rev(),
            );
        }

        Ok(None)
    }
}

/// How should the current query skip nodes
#[derive(Debug, Clone, Copy, Default, Ord, PartialOrd, Hash, Eq, PartialEq)]
pub enum SkipState {
    /// Skip anything in the depth-first search
    Any,
    /// Skip siblings
    Sibling,
    /// Do not skip
    #[default]
    None,
}

impl std::fmt::Display for SkipState {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Any => write!(f, "skip anything"),
            Self::Sibling => write!(f, "skip siblings"),
            Self::None => write!(f, "no skipping"),
        }
    }
}

impl From<bool> for SkipState {
    fn from(value: bool) -> Self {
        if value {
            Self::Sibling
        } else {
            Self::None
        }
    }
}

/// The type that represents queries as dependency graphs of query
/// labels.
///
/// The labels of vertices are query labels that match against forest
/// labels, whereas the labels of graphs indicate whether or not the
/// edge should allow skipping siblings before matching.
#[derive(Debug, Clone, Graph)]
pub struct Query<T: QueryLabel> {
    graph: SLGraph<SkipState>,
    vertex_labels: Vec<T>,
    root: Option<usize>,
}

impl<T: QueryLabel> Query<T> {
    /// Construct a new query from raw fields.
    pub fn new(graph: SLGraph<SkipState>, vertex_labels: Vec<T>, root: Option<usize>) -> Self {
        Self {
            graph,
            vertex_labels,
            root,
        }
    }

    /// Return the root of this query.
    ///
    /// This returns `None` if and only if the graph is empty.
    pub fn root(&self) -> Option<usize> {
        self.root
    }

    /// Return the label of the given node.
    ///
    /// This cannot be implemented as a method of the `LabelGraph`
    /// trait as the type differs from that of the labels.
    #[inline]
    pub fn label_of_vertex(&self, node: usize) -> Result<T, GError> {
        self.vertex_labels
            .get(node)
            .copied()
            .ok_or(GError::IndexOutOfBounds(node, self.vertex_labels.len()))
    }
}

impl<T: QueryLabel> Default for Query<T> {
    fn default() -> Self {
        let graph = Default::default();
        let vertex_labels = Vec::new();
        let root = None;

        Self {
            graph,
            vertex_labels,
            root,
        }
    }
}

// delegation of labelgraph

impl<T: QueryLabel> LabelGraph<SkipState> for Query<T> {
    type Iter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::Iter<'a>
    where
        Self: 'a;

    type TupleIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::TupleIter<'a>
    where
        Self: 'a;

    type LabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::LabelIter<'a>
    where
        Self: 'a;

    type EdgeLabelIter<'a> = <SLGraph<SkipState> as LabelGraph<SkipState>>::EdgeLabelIter<'a>
    where
        Self: 'a;

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

    fn find_children_with_label(
        &self,
        _node_id: usize,
        _label: &SkipState,
    ) -> Result<<Self as LabelGraph<SkipState>>::Iter<'_>, GError> {
        unimplemented!("Unsupported operation")
    }

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

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

    #[inline]
    fn has_edge_label(
        &self,
        node_id: usize,
        label: &SkipState,
        target: usize,
    ) -> Result<bool, GError> {
        self.graph.has_edge_label(node_id, label, target)
    }
}

#[derive(Debug, Clone)]
/// The type of errors that can occur when querying forests.
pub enum QRError {
    /// AN index is out of bounds.
    IndexOutOfBounds(usize, 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),
}

impl std::fmt::Display for QRError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            QRError::IndexOutOfBounds(n, b) => {
                write!(f, "index {n} out of bound {b}")
            }
            QRError::NodeNoLabel(n) => write!(f, "the node {n} has no label but should have one"),
            QRError::InvalidGraphError(g) => {
                write!(f, "an invalid error for forest iterators: {g}")
            }
        }
    }
}

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

impl From<GError> for QRError {
    fn from(value: GError) -> Self {
        match value {
            GError::IndexOutOfBounds(n, b) => Self::IndexOutOfBounds(n, b),
            _ => Self::InvalidGraphError(value),
        }
    }
}

/// An implementation of the forest iterator for querying purposes.
#[derive(Debug, Clone)]
pub struct QRun<T: QueryLabel> {
    /// The currently visited node.
    current: Option<usize>,
    /// The queries dependency graph.
    query: Query<T>,
    /// The packed nodes that can be used to change to another branch
    /// if needed.
    packs: Vec<usize>,
}

impl<T: QueryLabel> Default for QRun<T> {
    fn default() -> Self {
        let current = Default::default();
        let query = Default::default();
        let packs = Default::default();

        Self {
            current,
            query,
            packs,
        }
    }
}

impl<T: QueryLabel> ForestIter for QRun<T> {
    #[inline]
    fn current(&self) -> Option<usize> {
        self.current
    }

    type ForestLabel = <T as QueryLabel>::Obj;

    type Item<'a> = Option<&'a [usize]>
    where
        Self: 'a;

    type Error = QRError;

    #[allow(unused)]
    #[allow(clippy::collapsible_if)]
    fn next<F>(&mut self, forest: &F, root: usize) -> Result<State, Self::Error>
    where
        F: LabelGraph<ForestLabel<Self::ForestLabel>>,
    {
        let query_root = if let Some(r) = self.query.root() {
            r
        } else {
            return Ok(State::Finish);
        };

        #[derive(Debug, Clone, Copy)]
        enum Item<T: Copy + Clone + std::fmt::Debug> {
            Seen(T),
            Unseen(T),
        }

        use Item::*;

        impl<T: Copy + Clone + std::fmt::Debug> Item<T> {
            fn is_seen(self) -> bool {
                matches!(self, Self::Seen(_))
            }

            fn value(&self) -> T {
                match self {
                    Seen(v) => *v,
                    Unseen(v) => *v,
                }
            }
        }

        let query_len = self.query.nodes_len();

        let mut stack: Vec<Item<(SkipState, usize, usize)>> = Vec::with_capacity(query_len);

        stack.push(Unseen((SkipState::Any, root, query_root)));

        let mut parents_stack: Vec<usize> = Vec::with_capacity(query_len);

        let mut match_result = false;

        while let Some(item) = stack.pop() {
            if item.is_seen() {
                if match_result {
                    continue;
                }

                // fallback
            }

            let (state, top, qtop) = item.value();

            let top_label = forest.vertex_label(top)?.ok_or(QRError::NodeNoLabel(top))?;

            let query_label = self.query.label_of_vertex(qtop)?;

            if query_label.matches(top_label.label(), top_label.status()) {
                // Success branch

                match_result = true;

                // TODO: Deal with captures later
            } else {
                // Failure branch

                match_result = false;
            }
        }

        todo!()
    }

    #[inline]
    fn clear(&mut self) {
        self.current.take();
        self.packs.clear();
    }
}