fluidattacks-blends-domain 0.36.0

use alloc::collections::VecDeque;

use crate::stack::{StackGraph, StackNode, StackScope};
use crate::NodeId;

/// A symbol on a path's symbol stack.
#[derive(Clone, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub struct ScopedSymbol<'a> {
    /// The symbol's name.
    pub symbol: &'a str,
    /// The scope stack, top first, that a scoped push attached; `None` for a plain push.
    pub scopes: Option<VecDeque<NodeId>>,
}

/// The symbol and scope stacks a path carries through the graph, top first.
#[derive(Clone, PartialEq, Eq, Debug, Default)]
#[non_exhaustive]
pub struct StackState<'a> {
    /// Symbols still to resolve.
    pub symbols: VecDeque<ScopedSymbol<'a>>,
    /// Scopes a later jump can enter.
    pub scopes: VecDeque<NodeId>,
}

/// Why a node cannot be applied to a [`StackState`].
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
#[non_exhaustive]
pub enum TransitionError {
    /// A jump found no scope to enter.
    EmptyScopeStack,
    /// A pop found no symbol to consume.
    EmptySymbolStack,
    /// A pop found a different symbol on top.
    IncorrectPoppedSymbol,
    /// A scoped pop found a symbol without attached scopes.
    MissingAttachedScopes,
    /// A plain pop found a symbol with attached scopes.
    UnexpectedAttachedScopes,
    /// A scoped push attached a scope other paths cannot enter.
    UnknownAttachedScope,
    /// The node is not in the graph.
    UnknownNode,
}

impl<'a> StackState<'a> {
    /// An empty state.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Applies node `id` of `graph`, returning the scope to jump to, if any.
    ///
    /// # Errors
    ///
    /// Returns the [`TransitionError`] that blocks the node, leaving the state unchanged.
    pub fn apply(
        &mut self,
        graph: &'a StackGraph,
        id: NodeId,
    ) -> Result<Option<NodeId>, TransitionError> {
        match graph.nodes.get(&id).ok_or(TransitionError::UnknownNode)? {
            StackNode::PushSymbol(push) => self.push(&push.symbol, None),
            StackNode::PushScopedSymbol { push, scope } => {
                if !is_exported_scope(graph, *scope) {
                    return Err(TransitionError::UnknownAttachedScope);
                }
                let mut attached = self.scopes.clone();
                attached.push_front(*scope);
                self.push(&push.symbol, Some(attached));
            }
            StackNode::PopSymbol(pop) => {
                self.pop(&pop.symbol, false)?;
            }
            StackNode::PopScopedSymbol(pop) => {
                self.scopes = self.pop(&pop.symbol, true)?.scopes.unwrap_or_default();
            }
            StackNode::JumpTo => {
                return self
                    .scopes
                    .pop_front()
                    .map(Some)
                    .ok_or(TransitionError::EmptyScopeStack);
            }
            StackNode::DropScopes => self.scopes.clear(),
            StackNode::Root | StackNode::Scope(_) => {}
        }
        Ok(None)
    }

    fn push(&mut self, symbol: &'a str, scopes: Option<VecDeque<NodeId>>) {
        self.symbols.push_front(ScopedSymbol { symbol, scopes });
    }

    fn pop(&mut self, symbol: &str, scoped: bool) -> Result<ScopedSymbol<'a>, TransitionError> {
        let top = self
            .symbols
            .front()
            .ok_or(TransitionError::EmptySymbolStack)?;
        if top.symbol != symbol {
            return Err(TransitionError::IncorrectPoppedSymbol);
        }
        match (scoped, top.scopes.is_some()) {
            (true, false) => Err(TransitionError::MissingAttachedScopes),
            (false, true) => Err(TransitionError::UnexpectedAttachedScopes),
            _ => self
                .symbols
                .pop_front()
                .ok_or(TransitionError::EmptySymbolStack),
        }
    }
}

fn is_exported_scope(graph: &StackGraph, id: NodeId) -> bool {
    matches!(
        graph.nodes.get(&id),
        Some(StackNode::Scope(StackScope {
            is_exported: true,
            ..
        }))
    )
}

#[cfg(test)]
mod tests {
    use super::{ScopedSymbol, StackState, TransitionError};
    use crate::stack::{Definition, StackGraph, StackNode, StackScope, SymbolPop, SymbolPush};
    use crate::NodeId;
    use alloc::borrow::ToOwned;
    use alloc::collections::VecDeque;
    use alloc::vec::Vec;

    const EXPORTED: NodeId = NodeId(1);
    const LOCAL: NodeId = NodeId(2);

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

    fn pop(symbol: &str) -> SymbolPop {
        SymbolPop {
            symbol: symbol.to_owned(),
            precedence: 0,
            definition: Some(Definition::default()),
            import: None,
        }
    }

    fn graph(nodes: &[StackNode]) -> StackGraph {
        let mut graph = StackGraph::new();
        graph.add_node(
            EXPORTED,
            StackNode::Scope(StackScope {
                is_exported: true,
                scope_type: None,
            }),
        );
        graph.add_node(LOCAL, StackNode::Scope(StackScope::default()));
        for (id, node) in (10..).zip(nodes) {
            graph.add_node(NodeId(id), node.clone());
        }
        graph
    }

    fn run<'a>(
        graph: &'a StackGraph,
        state: &mut StackState<'a>,
    ) -> Result<Vec<NodeId>, TransitionError> {
        graph
            .nodes
            .keys()
            .filter(|id| id.0 >= 10)
            .filter_map(|id| state.apply(graph, *id).transpose())
            .collect()
    }

    fn symbols<'a>(state: &StackState<'a>) -> Vec<&'a str> {
        state.symbols.iter().map(|symbol| symbol.symbol).collect()
    }

    #[test]
    fn pushes_stack_symbols_with_the_latest_on_top() {
        let graph = graph(&[
            StackNode::PushSymbol(push("b")),
            StackNode::PushSymbol(push("a")),
        ]);
        let mut state = StackState::new();
        run(&graph, &mut state).unwrap();

        assert_eq!(symbols(&state), ["a", "b"]);
    }

    #[test]
    fn a_pop_consumes_the_matching_top_symbol() {
        let graph = graph(&[
            StackNode::PushSymbol(push("b")),
            StackNode::PushSymbol(push("a")),
            StackNode::PopSymbol(pop("a")),
        ]);
        let mut state = StackState::new();
        run(&graph, &mut state).unwrap();

        assert_eq!(symbols(&state), ["b"]);
    }

    fn apply_last(nodes: &[StackNode]) -> (Result<Option<NodeId>, TransitionError>, bool) {
        let graph = graph(nodes);
        let ids: Vec<NodeId> = graph
            .nodes
            .keys()
            .filter(|id| id.0 >= 10)
            .copied()
            .collect();
        let (last, setup) = ids.split_last().unwrap();
        let mut state = StackState::new();
        for id in setup {
            state.apply(&graph, *id).unwrap();
        }
        let before = state.clone();
        let result = state.apply(&graph, *last);
        (result, state == before)
    }

    #[test]
    fn a_pop_on_an_empty_stack_fails_without_changing_the_state() {
        assert_eq!(
            apply_last(&[StackNode::PopSymbol(pop("a"))]),
            (Err(TransitionError::EmptySymbolStack), true)
        );
    }

    #[test]
    fn a_pop_of_another_symbol_fails_without_changing_the_state() {
        assert_eq!(
            apply_last(&[
                StackNode::PushSymbol(push("b")),
                StackNode::PopSymbol(pop("a"))
            ]),
            (Err(TransitionError::IncorrectPoppedSymbol), true)
        );
    }

    #[test]
    fn a_scoped_pop_of_a_plain_symbol_fails_without_changing_the_state() {
        assert_eq!(
            apply_last(&[
                StackNode::PushSymbol(push("a")),
                StackNode::PopScopedSymbol(pop("a"))
            ]),
            (Err(TransitionError::MissingAttachedScopes), true)
        );
    }

    #[test]
    fn a_plain_pop_of_a_scoped_symbol_fails_without_changing_the_state() {
        assert_eq!(
            apply_last(&[
                StackNode::PushScopedSymbol {
                    push: push("a"),
                    scope: EXPORTED
                },
                StackNode::PopSymbol(pop("a"))
            ]),
            (Err(TransitionError::UnexpectedAttachedScopes), true)
        );
    }

    #[test]
    fn a_scoped_push_of_a_scope_hidden_from_other_paths_fails_without_changing_the_state() {
        assert_eq!(
            apply_last(&[StackNode::PushScopedSymbol {
                push: push("a"),
                scope: LOCAL
            }]),
            (Err(TransitionError::UnknownAttachedScope), true)
        );
    }

    #[test]
    fn a_jump_without_scopes_fails_without_changing_the_state() {
        assert_eq!(
            apply_last(&[StackNode::PushSymbol(push("a")), StackNode::JumpTo]),
            (Err(TransitionError::EmptyScopeStack), true)
        );
    }

    #[test]
    fn a_scoped_push_attaches_its_scope_over_the_current_scopes() {
        let graph = graph(&[StackNode::PushScopedSymbol {
            push: push("a"),
            scope: EXPORTED,
        }]);
        let mut state = StackState::new();
        state.scopes.push_front(LOCAL);
        run(&graph, &mut state).unwrap();

        assert_eq!(
            state.symbols.front(),
            Some(&ScopedSymbol {
                symbol: "a",
                scopes: Some(VecDeque::from([EXPORTED, LOCAL])),
            })
        );
    }

    #[test]
    fn a_scoped_pop_replaces_the_scopes_with_the_attached_ones() {
        let graph = graph(&[
            StackNode::PushScopedSymbol {
                push: push("a"),
                scope: EXPORTED,
            },
            StackNode::DropScopes,
            StackNode::PopScopedSymbol(pop("a")),
        ]);
        let mut state = StackState::new();
        run(&graph, &mut state).unwrap();

        assert_eq!(state.scopes, [EXPORTED]);
    }

    #[test]
    fn a_jump_enters_the_top_scope_and_removes_it() {
        let graph = graph(&[StackNode::JumpTo]);
        let mut state = StackState::new();
        state.scopes = VecDeque::from([EXPORTED, LOCAL]);

        assert_eq!(run(&graph, &mut state), Ok(Vec::from([EXPORTED])));
        assert_eq!(state.scopes, [LOCAL]);
    }

    #[test]
    fn dropping_scopes_keeps_the_symbols() {
        let graph = graph(&[StackNode::PushSymbol(push("a")), StackNode::DropScopes]);
        let mut state = StackState::new();
        state.scopes.push_front(EXPORTED);
        run(&graph, &mut state).unwrap();

        assert_eq!((symbols(&state), state.scopes.len()), (Vec::from(["a"]), 0));
    }

    #[test]
    fn roots_and_scopes_leave_the_state_unchanged() {
        let mut graph = graph(&[StackNode::Root]);
        graph.add_node(NodeId(11), StackNode::Scope(StackScope::default()));
        let mut state = StackState::new();
        state.scopes.push_front(EXPORTED);
        let before = state.clone();

        assert_eq!(run(&graph, &mut state), Ok(Vec::new()));
        assert_eq!(state, before);
    }

    #[test]
    fn a_missing_node_cannot_be_applied() {
        let graph = graph(&[]);

        assert_eq!(
            StackState::new().apply(&graph, NodeId(99)),
            Err(TransitionError::UnknownNode)
        );
    }
}