shex_ast/ir/
dependency_graph.rs

1use std::fmt::Display;
2
3use crate::ShapeLabelIdx;
4use petgraph::dot::{Config, Dot};
5use petgraph::graphmap::GraphMap;
6use petgraph::visit::EdgeRef;
7
8#[derive(Debug, Default)]
9pub struct DependencyGraph {
10    graph: GraphMap<ShapeLabelIdx, PosNeg, petgraph::Directed>,
11}
12
13impl DependencyGraph {
14    pub fn new() -> Self {
15        Self::default()
16    }
17
18    pub fn add_edge(&mut self, from: ShapeLabelIdx, to: ShapeLabelIdx, pos_neg: PosNeg) {
19        self.graph.add_edge(from, to, pos_neg);
20    }
21
22    pub fn neg_cycles(&self) -> Vec<Vec<(ShapeLabelIdx, ShapeLabelIdx, Vec<ShapeLabelIdx>)>> {
23        let mut result = Vec::new();
24        let scc = petgraph::algo::tarjan_scc(&self.graph);
25        for component in &scc {
26            let mut neg_cycle = Vec::new();
27            for node in component.iter().as_slice() {
28                let edges = self
29                    .graph
30                    .edges_directed(*node, petgraph::Direction::Outgoing);
31                for edge in edges {
32                    if component.contains(&edge.target()) && edge.weight().is_neg() {
33                        let mut shapes = Vec::new();
34                        for node in component.iter() {
35                            shapes.push(*node);
36                        }
37                        let target = edge.target();
38                        neg_cycle.push((*node, target, shapes));
39                        break;
40                    }
41                }
42            }
43            if !neg_cycle.is_empty() {
44                result.push(neg_cycle);
45            }
46        }
47        result
48    }
49
50    pub fn has_neg_cycle(&self) -> bool {
51        let neg_cycles = self.neg_cycles();
52        !neg_cycles.is_empty()
53    }
54
55    pub fn all_edges(&self) -> DependencyGraphIter {
56        DependencyGraphIter {
57            inner: self.graph.all_edges(),
58        }
59    }
60}
61
62impl Display for DependencyGraph {
63    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
64        write!(
65            f,
66            "{:?}",
67            Dot::with_config(&self.graph, &[Config::GraphContentOnly])
68        )
69    }
70}
71
72/// Iterator over the edges of the dependency graph.
73/// The iterator yields tuples of the form (from, posneg, to).
74pub struct DependencyGraphIter<'a> {
75    inner: petgraph::graphmap::AllEdges<'a, ShapeLabelIdx, PosNeg, petgraph::Directed>,
76}
77impl Iterator for DependencyGraphIter<'_> {
78    type Item = (ShapeLabelIdx, PosNeg, ShapeLabelIdx);
79
80    fn next(&mut self) -> Option<Self::Item> {
81        self.inner
82            .next()
83            .map(|(from, to, posneg)| (from, *posneg, to))
84    }
85}
86
87#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
88pub enum PosNeg {
89    #[default]
90    Pos,
91    Neg,
92}
93
94impl PosNeg {
95    pub fn is_pos(&self) -> bool {
96        matches!(self, PosNeg::Pos)
97    }
98
99    pub fn is_neg(&self) -> bool {
100        matches!(self, PosNeg::Neg)
101    }
102
103    pub fn pos() -> PosNeg {
104        PosNeg::Pos
105    }
106
107    pub fn neg() -> PosNeg {
108        PosNeg::Neg
109    }
110
111    pub fn change(&self) -> PosNeg {
112        match self {
113            PosNeg::Pos => PosNeg::Neg,
114            PosNeg::Neg => PosNeg::Pos,
115        }
116    }
117}
118
119impl Display for PosNeg {
120    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
121        match self {
122            PosNeg::Pos => write!(f, "[+]"),
123            PosNeg::Neg => write!(f, "[-]"),
124        }
125    }
126}
127
128#[cfg(test)]
129mod tests {
130
131    #[test]
132    fn test_neg_cycle_no() {
133        use super::*;
134
135        let mut graph = DependencyGraph::new();
136        graph.add_edge(ShapeLabelIdx::from(0), ShapeLabelIdx::from(1), PosNeg::Pos);
137        graph.add_edge(ShapeLabelIdx::from(1), ShapeLabelIdx::from(0), PosNeg::Pos);
138        assert!(!graph.has_neg_cycle());
139    }
140
141    #[test]
142    fn test_neg_cycle_yes() {
143        use super::*;
144
145        let mut graph = DependencyGraph::new();
146        graph.add_edge(ShapeLabelIdx::from(0), ShapeLabelIdx::from(1), PosNeg::Pos);
147        graph.add_edge(ShapeLabelIdx::from(1), ShapeLabelIdx::from(0), PosNeg::Neg);
148        assert!(graph.has_neg_cycle());
149    }
150}
shex_ast/ir/dependency_graph.rs

shex_ast/ir/
dependency_graph.rs
