fluidattacks-blends-domain 0.41.0

use alloc::vec::Vec;

use crate::stack::resolve::{
    PartialBindings, PartialSymbolStack, SymbolStackVariable, TransitionError, UnifyError,
};
use crate::stack::{StackGraph, StackNode};
use crate::NodeId;

/// An edge a partial path follows.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PathEdge {
    /// The node the edge leaves.
    pub source: NodeId,
    /// The edge's precedence.
    pub precedence: i64,
}

/// A walk from `start` to `end`: the symbol stack it needs on entry and the one it leaves.
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct PartialPath<'a> {
    /// The node the walk starts at.
    pub start: NodeId,
    /// The node the walk ends at.
    pub end: NodeId,
    /// The symbol stack the walk needs on entry.
    pub pre: PartialSymbolStack<'a>,
    /// The symbol stack the walk leaves.
    pub post: PartialSymbolStack<'a>,
    /// The edges followed, in order.
    pub edges: Vec<PathEdge>,
}

/// Why two partial paths do not form one walk.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum PathError {
    /// The second path does not start where the first one ends.
    DisjointPaths,
    /// The node where the paths meet does not match the stacks around it.
    Transition(TransitionError),
    /// The stack one path leaves does not match the stack the other needs.
    Unify(UnifyError),
    /// The stack left ends in a variable the stack needed lacks.
    UnboundVariable,
    /// Renaming the variables apart ran past the last variable number.
    VariableOverflow,
}

impl From<TransitionError> for PathError {
    fn from(error: TransitionError) -> Self {
        Self::Transition(error)
    }
}

impl From<UnifyError> for PathError {
    fn from(error: UnifyError) -> Self {
        Self::Unify(error)
    }
}

impl PartialPath<'_> {
    /// This walk followed by `rhs`, which must start where this one ends.
    ///
    /// # Errors
    ///
    /// Returns the [`PathError`] that keeps the walks apart.
    pub fn concatenate(&self, graph: &StackGraph, rhs: &Self) -> Result<Self, PathError> {
        if self.end != rhs.start {
            return Err(PathError::DisjointPaths);
        }
        let largest = self
            .pre
            .variable
            .max(self.post.variable)
            .map_or(0, SymbolStackVariable::get);
        let rhs_pre = rhs
            .pre
            .with_offset(largest)
            .ok_or(PathError::VariableOverflow)?;
        let rhs_post = rhs
            .post
            .with_offset(largest)
            .ok_or(PathError::VariableOverflow)?;
        let (left, right) = match graph
            .nodes
            .get(&self.end)
            .ok_or(TransitionError::UnknownNode)?
        {
            StackNode::PushSymbol(push) => (pop_top(&self.post, &push.symbol)?, rhs_pre),
            StackNode::PopSymbol(pop) => (self.post.clone(), pop_top(&rhs_pre, &pop.symbol)?),
            StackNode::Root | StackNode::Scope(_) => (self.post.clone(), rhs_pre),
        };
        let mut bindings = PartialBindings::new();
        bindings.unify(&left, &right)?;
        let pre = self.pre.apply_bindings(&bindings);
        let post = rhs_post.apply_bindings(&bindings);
        if post.variable.is_some() && post.variable != pre.variable {
            return Err(PathError::UnboundVariable);
        }
        Ok(Self {
            start: self.start,
            end: rhs.end,
            pre,
            post,
            edges: self.edges.iter().chain(&rhs.edges).copied().collect(),
        })
    }
}

fn pop_top<'a>(
    symbols: &PartialSymbolStack<'a>,
    symbol: &str,
) -> Result<PartialSymbolStack<'a>, TransitionError> {
    let mut rest = symbols.clone();
    match rest.symbols.pop_front() {
        None => Err(TransitionError::EmptySymbolStack),
        Some(top) if top != symbol => Err(TransitionError::IncorrectPoppedSymbol),
        Some(_) => Ok(rest),
    }
}

#[cfg(test)]
mod tests {
    use super::{PartialPath, PathEdge, PathError};
    use crate::stack::resolve::{
        PartialSymbolStack, SymbolStackVariable, TransitionError, UnifyError,
    };
    use crate::stack::{Definition, StackGraph, StackNode, StackScope, SymbolPop, SymbolPush};
    use crate::NodeId;
    use alloc::borrow::ToOwned;
    use alloc::vec::Vec;

    const PUSH_X: NodeId = NodeId(10);
    const PUSH_Y: NodeId = NodeId(11);
    const SCOPE: NodeId = NodeId(20);
    const OTHER_SCOPE: NodeId = NodeId(21);
    const POP_X: NodeId = NodeId(30);

    fn push(symbol: &str) -> StackNode {
        StackNode::PushSymbol(SymbolPush {
            symbol: symbol.to_owned(),
            precedence: 0,
            is_reference: true,
        })
    }

    fn graph() -> StackGraph {
        let mut graph = StackGraph::new();
        graph.add_node(PUSH_X, push("x"));
        graph.add_node(PUSH_Y, push("y"));
        graph.add_node(SCOPE, StackNode::Scope(StackScope::default()));
        graph.add_node(OTHER_SCOPE, StackNode::Scope(StackScope::default()));
        graph.add_node(
            POP_X,
            StackNode::PopSymbol(SymbolPop {
                symbol: "x".to_owned(),
                precedence: 0,
                definition: Some(Definition::default()),
                import: None,
            }),
        );
        graph
    }

    fn symbols<'a>(names: &[&'a str], variable: Option<u32>) -> PartialSymbolStack<'a> {
        PartialSymbolStack::new(
            names.iter().copied().collect(),
            variable.and_then(SymbolStackVariable::new),
        )
    }

    fn path<'a>(
        start: NodeId,
        end: NodeId,
        pre: PartialSymbolStack<'a>,
        post: PartialSymbolStack<'a>,
    ) -> PartialPath<'a> {
        PartialPath {
            start,
            end,
            pre,
            post,
            edges: Vec::new(),
        }
    }

    fn through(start: NodeId, end: NodeId) -> PartialPath<'static> {
        path(start, end, symbols(&[], Some(1)), symbols(&[], Some(1)))
    }

    #[test]
    fn a_reference_path_joined_with_a_definition_path_leaves_the_stack_as_it_was() {
        let graph = graph();
        let reference = path(
            PUSH_X,
            SCOPE,
            symbols(&[], Some(1)),
            symbols(&["x"], Some(1)),
        );
        let definition = path(
            SCOPE,
            POP_X,
            symbols(&["x"], Some(1)),
            symbols(&[], Some(1)),
        );

        assert_eq!(
            reference.concatenate(&graph, &definition),
            Ok(through(PUSH_X, POP_X))
        );
    }

    #[test]
    fn paths_that_do_not_meet_do_not_concatenate() {
        assert_eq!(
            through(PUSH_X, SCOPE).concatenate(&graph(), &through(OTHER_SCOPE, POP_X)),
            Err(PathError::DisjointPaths)
        );
    }

    #[test]
    fn a_push_where_the_paths_meet_is_counted_once() {
        let graph = graph();
        let lhs = path(
            SCOPE,
            PUSH_X,
            symbols(&[], Some(1)),
            symbols(&["x"], Some(1)),
        );
        let rhs = path(
            PUSH_X,
            PUSH_Y,
            symbols(&[], Some(1)),
            symbols(&["y", "x"], Some(1)),
        );

        assert_eq!(
            lhs.concatenate(&graph, &rhs).map(|joined| joined.post),
            Ok(symbols(&["y", "x"], Some(1)))
        );
    }

    #[test]
    fn a_pop_where_the_paths_meet_is_required_once() {
        let graph = graph();
        let lhs = path(
            SCOPE,
            POP_X,
            symbols(&["x"], Some(1)),
            symbols(&[], Some(1)),
        );
        let rhs = path(
            POP_X,
            OTHER_SCOPE,
            symbols(&["x"], Some(1)),
            symbols(&[], Some(1)),
        );

        assert_eq!(
            lhs.concatenate(&graph, &rhs).map(|joined| joined.pre),
            Ok(symbols(&["x"], Some(1)))
        );
    }

    #[test]
    fn a_push_of_another_symbol_where_the_paths_meet_does_not_concatenate() {
        let lhs = path(
            SCOPE,
            PUSH_X,
            symbols(&[], Some(1)),
            symbols(&["y"], Some(1)),
        );

        assert_eq!(
            lhs.concatenate(&graph(), &through(PUSH_X, PUSH_Y)),
            Err(PathError::Transition(
                TransitionError::IncorrectPoppedSymbol
            ))
        );
    }

    #[test]
    fn a_symbol_left_that_the_next_path_does_not_need_does_not_concatenate() {
        let lhs = path(
            PUSH_X,
            SCOPE,
            symbols(&[], Some(1)),
            symbols(&["x"], Some(1)),
        );
        let rhs = path(
            SCOPE,
            OTHER_SCOPE,
            symbols(&["y"], Some(1)),
            symbols(&[], Some(1)),
        );

        assert_eq!(
            lhs.concatenate(&graph(), &rhs),
            Err(PathError::Unify(UnifyError))
        );
    }

    #[test]
    fn the_variables_of_the_second_path_are_renamed_apart_from_the_first() {
        let graph = graph();
        let lhs = path(
            PUSH_X,
            SCOPE,
            symbols(&[], Some(1)),
            symbols(&["x"], Some(1)),
        );
        let rhs = path(
            SCOPE,
            OTHER_SCOPE,
            symbols(&[], Some(1)),
            symbols(&["y"], Some(1)),
        );

        assert_eq!(
            lhs.concatenate(&graph, &rhs).map(|joined| joined.post),
            Ok(symbols(&["y", "x"], Some(1)))
        );
    }

    #[test]
    fn renaming_past_the_last_variable_number_does_not_concatenate() {
        let rhs = path(
            SCOPE,
            OTHER_SCOPE,
            symbols(&[], Some(u32::MAX)),
            symbols(&[], Some(u32::MAX)),
        );

        assert_eq!(
            through(PUSH_X, SCOPE).concatenate(&graph(), &rhs),
            Err(PathError::VariableOverflow)
        );
    }

    #[test]
    fn a_variable_left_that_was_not_needed_does_not_concatenate() {
        let lhs = path(PUSH_X, SCOPE, symbols(&[], None), symbols(&[], Some(1)));

        assert_eq!(
            lhs.concatenate(&graph(), &through(SCOPE, OTHER_SCOPE)),
            Err(PathError::UnboundVariable)
        );
    }

    #[test]
    fn the_joined_path_follows_the_edges_of_both_in_order() {
        let edge = |source| PathEdge {
            source,
            precedence: 0,
        };
        let lhs = PartialPath {
            edges: Vec::from([edge(PUSH_X)]),
            ..through(PUSH_X, SCOPE)
        };
        let rhs = PartialPath {
            edges: Vec::from([edge(SCOPE)]),
            ..through(SCOPE, OTHER_SCOPE)
        };

        assert_eq!(
            lhs.concatenate(&graph(), &rhs).map(|joined| joined.edges),
            Ok(Vec::from([edge(PUSH_X), edge(SCOPE)]))
        );
    }
}