fluidattacks-blends-domain 0.6.0

//! Counterpart of `blends/path_search/utils.py`.

use alloc::vec;
use alloc::vec::Vec;

use crate::path_search::Path;
use crate::query::{lookup_first_cfg_parent, pred_cfg};
use crate::syntax::SyntaxGraph;
use crate::NodeId;

pub struct BackwardPaths<'a> {
    graph: &'a SyntaxGraph,
    stack: Vec<Path>,
}

impl Iterator for BackwardPaths<'_> {
    type Item = Path;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some(path) = self.stack.pop() {
            let Some(&tail) = path.last() else {
                continue;
            };
            let parents: Vec<NodeId> = pred_cfg(self.graph, tail, None)
                .into_iter()
                .filter(|parent| !path.contains(parent))
                .collect();
            if parents.is_empty() {
                return Some(path);
            }
            for parent in parents.into_iter().rev() {
                let mut next = path.clone();
                next.push(parent);
                self.stack.push(next);
            }
        }
        None
    }
}

#[must_use]
pub fn iter_backward_paths(graph: &SyntaxGraph, cfg_n_id: NodeId) -> BackwardPaths<'_> {
    BackwardPaths {
        graph,
        stack: vec![vec![cfg_n_id]],
    }
}

#[must_use]
pub fn get_backward_paths(graph: &SyntaxGraph, n_id: NodeId, limit: Option<usize>) -> Vec<Path> {
    let cfg_id = lookup_first_cfg_parent(graph, n_id);
    let paths = iter_backward_paths(graph, cfg_id);
    match limit.filter(|&value| value != 0) {
        Some(value) => paths.take(value.saturating_sub(1)).collect(),
        None => paths.collect(),
    }
}

#[cfg(test)]
mod tests {
    use super::{get_backward_paths, iter_backward_paths};
    use crate::syntax::{SyntaxGraph, SyntaxNode};
    use crate::NodeId;
    use alloc::vec::Vec;

    fn node(graph: &mut SyntaxGraph, id: u64) {
        graph.add_node(NodeId(id), SyntaxNode::ExecutionBlock);
    }

    #[test]
    fn linear_chain_yields_one_path_to_the_root() {
        let mut graph = SyntaxGraph::new();
        node(&mut graph, 1);
        node(&mut graph, 2);
        node(&mut graph, 3);
        graph.add_cfg_edge(NodeId(1), NodeId(2));
        graph.add_cfg_edge(NodeId(2), NodeId(3));

        assert_eq!(
            get_backward_paths(&graph, NodeId(3), Some(100)),
            [[NodeId(3), NodeId(2), NodeId(1)]]
        );
    }

    #[test]
    fn iter_yields_every_path_unbounded_from_the_given_cfg_node() {
        let mut graph = SyntaxGraph::new();
        node(&mut graph, 1);
        node(&mut graph, 2);
        node(&mut graph, 3);
        graph.add_cfg_edge(NodeId(1), NodeId(3));
        graph.add_cfg_edge(NodeId(2), NodeId(3));

        let paths: Vec<_> = iter_backward_paths(&graph, NodeId(3)).collect();
        assert_eq!(
            paths,
            [vec![NodeId(3), NodeId(1)], vec![NodeId(3), NodeId(2)],]
        );
    }

    #[test]
    fn a_branch_upstream_yields_one_path_per_predecessor_in_id_order() {
        let mut graph = SyntaxGraph::new();
        node(&mut graph, 1);
        node(&mut graph, 2);
        node(&mut graph, 3);
        node(&mut graph, 4);
        graph.add_cfg_edge(NodeId(1), NodeId(3));
        graph.add_cfg_edge(NodeId(2), NodeId(3));
        graph.add_cfg_edge(NodeId(3), NodeId(4));

        assert_eq!(
            get_backward_paths(&graph, NodeId(4), Some(100)),
            [
                vec![NodeId(4), NodeId(3), NodeId(1)],
                vec![NodeId(4), NodeId(3), NodeId(2)],
            ]
        );
    }

    #[test]
    fn a_back_edge_cycle_terminates() {
        let mut graph = SyntaxGraph::new();
        node(&mut graph, 1);
        node(&mut graph, 2);
        graph.add_cfg_edge(NodeId(1), NodeId(2));
        graph.add_cfg_edge(NodeId(2), NodeId(1));

        assert_eq!(
            get_backward_paths(&graph, NodeId(2), Some(100)),
            [[NodeId(2), NodeId(1)]]
        );
    }

    #[test]
    fn the_limit_caps_the_number_of_paths() {
        let mut graph = SyntaxGraph::new();
        for id in 1..=4 {
            node(&mut graph, id);
        }
        graph.add_cfg_edge(NodeId(1), NodeId(4));
        graph.add_cfg_edge(NodeId(2), NodeId(4));
        graph.add_cfg_edge(NodeId(3), NodeId(4));

        assert_eq!(get_backward_paths(&graph, NodeId(4), Some(3)).len(), 2);
    }

    #[test]
    fn a_none_limit_returns_every_path_unbounded() {
        let mut graph = SyntaxGraph::new();
        node(&mut graph, 1);
        node(&mut graph, 2);
        node(&mut graph, 3);
        graph.add_cfg_edge(NodeId(1), NodeId(3));
        graph.add_cfg_edge(NodeId(2), NodeId(3));

        assert_eq!(
            get_backward_paths(&graph, NodeId(3), None),
            [vec![NodeId(3), NodeId(1)], vec![NodeId(3), NodeId(2)]]
        );
    }
}