1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
use crate::ir::ShapeLabelIdx;
pub(crate) use crate::ir::dg::iterator::DependencyGraphIter;
pub(crate) use crate::ir::dg::pos_neg::PosNeg;
use petgraph::algo::{is_cyclic_directed, tarjan_scc};
use petgraph::prelude::{EdgeRef, GraphMap};
use petgraph::{Directed, Outgoing};
use std::collections::HashMap;
use std::fmt::{Display, Formatter};
mod iterator;
mod pos_neg;
mod stratification;
pub use stratification::ShapeRecursionKind;
#[derive(Default, Debug, Clone)]
pub struct DependencyGraph {
graph: GraphMap<ShapeLabelIdx, PosNeg, Directed>,
}
impl DependencyGraph {
pub fn new() -> Self {
DependencyGraph { graph: GraphMap::new() }
}
pub fn add_edge(&mut self, from: ShapeLabelIdx, to: ShapeLabelIdx, pos_neg: PosNeg) {
self.graph.add_edge(from, to, pos_neg);
}
/// Check if the dependency graph has any cycle (including positive cycles).
pub fn has_cycles(&self) -> bool {
is_cyclic_directed(&self.graph)
}
pub fn cycles(&self) -> Vec<Vec<ShapeLabelIdx>> {
let scc = tarjan_scc(&self.graph);
scc.into_iter().filter(|component| component.len() > 1).collect()
}
pub fn all_edges(&self) -> DependencyGraphIter<'_> {
DependencyGraphIter::new(self.graph.all_edges())
}
/// Returns shape indices grouped into topological levels such that dependencies
/// appear at lower levels than the shapes that depend on them.
///
/// Level 0 contains shapes that do not depend on any other shape.
/// Level N contains shapes whose dependencies are all in levels 0..N-1.
///
/// Shapes involved in a cycle are never reachable via Kahn's algorithm proper
/// (their `remaining_deps` count never reaches zero), so they're collected into
/// one extra trailing level instead of being silently dropped. Validating that
/// level relies on the engine's own recursive-reference cutting (see
/// `crate::validator::recursion`) rather than on level ordering to terminate.
pub fn topological_levels(&self) -> Vec<Vec<ShapeLabelIdx>> {
// Edge A -> B means "A depends on B".
// We want to validate B before A, so we assign B a lower level.
//
// Algorithm: Kahn's on the dependency graph using out-degree.
// - remaining_deps[A] = number of shapes A still depends on
// - dependents_of[B] = shapes that depend on B
//
// Level 0: shapes with remaining_deps == 0 (depend on nothing).
// When a shape is added to a level, decrement remaining_deps of every
// shape that depends on it; newly-zero shapes enter the next level.
let mut remaining_deps: HashMap<ShapeLabelIdx, usize> = HashMap::new();
let mut dependents_of: HashMap<ShapeLabelIdx, Vec<ShapeLabelIdx>> = HashMap::new();
for node in self.graph.nodes() {
remaining_deps.entry(node).or_insert(0);
}
for node in self.graph.nodes() {
for edge in self.graph.edges_directed(node, Outgoing) {
let to = edge.target();
*remaining_deps.get_mut(&node).unwrap() += 1;
dependents_of.entry(to).or_default().push(node);
}
}
let mut levels: Vec<Vec<ShapeLabelIdx>> = Vec::new();
let mut placed: std::collections::HashSet<ShapeLabelIdx> = std::collections::HashSet::new();
let mut current: Vec<ShapeLabelIdx> = remaining_deps
.iter()
.filter(|&(_, count)| *count == 0)
.map(|(&node, _)| node)
.collect();
current.sort_unstable();
while !current.is_empty() {
placed.extend(current.iter().copied());
levels.push(current.clone());
let mut next: Vec<ShapeLabelIdx> = Vec::new();
for done in ¤t {
for dependent in dependents_of.get(done).into_iter().flatten() {
let count = remaining_deps.get_mut(dependent).unwrap();
*count -= 1;
if *count == 0 {
next.push(*dependent);
}
}
}
next.sort_unstable();
current = next;
}
// Shapes still stuck with remaining_deps > 0 are part of a cycle (or
// depend, transitively, only on cyclic shapes) and were never placed
// above. Group them into one trailing level instead of dropping them.
let mut leftover: Vec<ShapeLabelIdx> = remaining_deps
.keys()
.copied()
.filter(|node| !placed.contains(node))
.collect();
if !leftover.is_empty() {
leftover.sort_unstable();
levels.push(leftover);
}
levels
}
}
impl Display for DependencyGraph {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
writeln!(f, "Dependency Graph:")?;
for (from, posneg, to) in self.all_edges() {
writeln!(f, " {} --{}--> {}", from, posneg, to)?;
}
Ok(())
}
}