fluidattacks-blends-domain 0.38.0

use alloc::collections::{BTreeSet, VecDeque};
use alloc::vec::Vec;

use crate::stack::resolve::{PartialPath, PathEdge, TransitionError};
use crate::stack::{StackGraph, StackNode};
use crate::NodeId;

/// Every walk of `graph` from one endpoint to the next, without passing another endpoint.
///
/// Endpoints are references, definitions and the root.
#[must_use]
pub fn minimal_partial_paths(graph: &StackGraph) -> Vec<PartialPath<'_>> {
    graph
        .nodes
        .iter()
        .filter(|(_, node)| is_endpoint(node))
        .flat_map(|(id, _)| PartialPath::seed(graph, *id))
        .flat_map(|seed| paths_from(graph, seed))
        .collect()
}

fn paths_from<'a>(graph: &'a StackGraph, seed: PartialPath<'a>) -> Vec<PartialPath<'a>> {
    let mut visited = BTreeSet::new();
    let mut queue = VecDeque::from([seed]);
    let mut paths = Vec::new();
    while let Some(path) = queue.pop_front() {
        for (sink, precedence) in graph.successors(path.end) {
            let Ok(next) = append(graph, &path, sink, precedence) else {
                continue;
            };
            if !visited.insert((next.end, next.pre.clone(), next.post.clone())) {
                continue;
            }
            if graph.nodes.get(&sink).is_some_and(is_endpoint) {
                paths.push(next);
            } else {
                queue.push_back(next);
            }
        }
    }
    paths
}

fn append<'a>(
    graph: &'a StackGraph,
    path: &PartialPath<'a>,
    sink: NodeId,
    precedence: i64,
) -> Result<PartialPath<'a>, TransitionError> {
    let mut next = path.clone();
    match graph.nodes.get(&sink).ok_or(TransitionError::UnknownNode)? {
        StackNode::PushSymbol(push) => next.post.symbols.push_front(&push.symbol),
        StackNode::PopSymbol(pop) => match next.post.symbols.pop_front() {
            Some(top) if top == pop.symbol => {}
            Some(_) => return Err(TransitionError::IncorrectPoppedSymbol),
            None if next.post.variable.is_some() => next.pre.symbols.push_back(&pop.symbol),
            None => return Err(TransitionError::EmptySymbolStack),
        },
        StackNode::Root | StackNode::Scope(_) => {}
    }
    next.end = sink;
    next.edges.push(PathEdge {
        source: path.end,
        precedence,
    });
    Ok(next)
}

fn is_endpoint(node: &StackNode) -> bool {
    node.is_reference() || node.is_definition() || matches!(node, StackNode::Root)
}

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

    const ROOT: NodeId = NodeId(1);
    const REFERENCE: NodeId = NodeId(2);
    const SCOPE: NodeId = NodeId(3);
    const OTHER_SCOPE: NodeId = NodeId(4);
    const DEFINITION: NodeId = NodeId(5);
    const OTHER_DEFINITION: NodeId = NodeId(6);
    const RELAY: NodeId = NodeId(7);

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

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

    fn node(id: NodeId) -> StackNode {
        match id {
            ROOT => StackNode::Root,
            REFERENCE => push("x", true),
            RELAY => push("m", false),
            DEFINITION => pop("x"),
            OTHER_DEFINITION => pop("y"),
            _ => StackNode::Scope(StackScope::default()),
        }
    }

    fn graph(edges: &[(NodeId, NodeId)]) -> StackGraph {
        let mut graph = StackGraph::new();
        for (source, sink) in edges {
            graph.add_node(*source, node(*source));
            graph.add_node(*sink, node(*sink));
            graph.add_edge(*source, *sink, 0);
        }
        graph
    }

    fn stack<'a>(symbols: &[&'a str]) -> PartialSymbolStack<'a> {
        PartialSymbolStack::new(
            symbols.iter().copied().collect(),
            Some(SymbolStackVariable::INITIAL),
        )
    }

    type Walk<'a> = (
        NodeId,
        NodeId,
        PartialSymbolStack<'a>,
        PartialSymbolStack<'a>,
    );

    fn walks(graph: &StackGraph) -> Vec<Walk<'_>> {
        minimal_partial_paths(graph)
            .into_iter()
            .map(|path| (path.start, path.end, path.pre, path.post))
            .collect()
    }

    #[test]
    fn a_reference_reaches_the_definition_of_its_symbol_with_the_stack_as_it_found_it() {
        assert_eq!(
            walks(&graph(&[(REFERENCE, SCOPE), (SCOPE, DEFINITION)])),
            [(REFERENCE, DEFINITION, stack(&[]), stack(&[]))]
        );
    }

    #[test]
    fn a_reference_does_not_reach_the_definition_of_another_symbol() {
        assert_eq!(
            walks(&graph(&[(REFERENCE, SCOPE), (SCOPE, OTHER_DEFINITION)])),
            []
        );
    }

    #[test]
    fn a_definition_reached_from_the_root_needs_its_symbol_on_the_stack() {
        assert_eq!(
            walks(&graph(&[(ROOT, DEFINITION)])),
            [(ROOT, DEFINITION, stack(&["x"]), stack(&[]))]
        );
    }

    #[test]
    fn a_relay_push_leaves_its_symbol_without_ending_the_walk() {
        assert_eq!(
            walks(&graph(&[(REFERENCE, RELAY), (RELAY, ROOT)])),
            [(REFERENCE, ROOT, stack(&[]), stack(&["m", "x"]))]
        );
    }

    #[test]
    fn a_walk_ends_at_the_first_endpoint_it_reaches() {
        assert_eq!(
            walks(&graph(&[
                (SCOPE, ROOT),
                (ROOT, REFERENCE),
                (REFERENCE, SCOPE)
            ])),
            [
                (ROOT, REFERENCE, stack(&[]), stack(&["x"])),
                (REFERENCE, ROOT, stack(&[]), stack(&["x"])),
            ]
        );
    }

    #[test]
    fn a_cycle_without_endpoints_ends_the_search_without_walks() {
        assert_eq!(
            walks(&graph(&[
                (REFERENCE, SCOPE),
                (SCOPE, OTHER_SCOPE),
                (OTHER_SCOPE, SCOPE)
            ])),
            []
        );
    }

    #[test]
    fn two_routes_with_the_same_stacks_give_one_walk() {
        assert_eq!(
            walks(&graph(&[
                (REFERENCE, SCOPE),
                (REFERENCE, OTHER_SCOPE),
                (SCOPE, DEFINITION),
                (OTHER_SCOPE, DEFINITION),
            ])),
            [(REFERENCE, DEFINITION, stack(&[]), stack(&[]))]
        );
    }

    #[test]
    fn a_walk_follows_its_edges_from_the_start() {
        let graph = graph(&[(REFERENCE, SCOPE), (SCOPE, DEFINITION)]);
        let edge = |source| PathEdge {
            source,
            precedence: 0,
        };

        assert_eq!(
            minimal_partial_paths(&graph)
                .into_iter()
                .map(|path| path.edges)
                .collect::<Vec<_>>(),
            [Vec::from([edge(REFERENCE), edge(SCOPE)])]
        );
    }
}