grex_core/pack/validate/
cycle.rs

1//! Post-hoc cycle detector over an assembled [`PackGraph`].
2//!
3//! The walker detects cycles during recursion, so in normal use this
4//! validator is redundant. It exists as a **defensive** check so:
5//!
6//! * Manually-assembled test fixtures (or future graph mutation APIs)
7//!   cannot smuggle a cycle past validation.
8//! * A future IPC-backed walker that fails to enforce cycle detection
9//!   cannot silently produce a bad graph.
10//!
11//! Implementation: depth-first traversal of `Child` edges (cycles in the
12//! owned-subtree space are what the walker-specified invariant forbids).
13//! `DependsOn` edges are non-owning references and are excluded from the
14//! check.
15
16use std::collections::HashSet;
17
18use super::{GraphValidator, PackValidationError};
19use crate::tree::{EdgeKind, PackGraph};
20
21/// Detect cycles among `Child` edges of a pack graph.
22pub struct CycleValidator;
23
24impl GraphValidator for CycleValidator {
25    fn name(&self) -> &'static str {
26        "graph_cycle"
27    }
28
29    fn check(&self, graph: &PackGraph) -> Vec<PackValidationError> {
30        let mut errs = Vec::new();
31        let mut visited: HashSet<usize> = HashSet::new();
32        for start in 0..graph.nodes().len() {
33            if visited.contains(&start) {
34                continue;
35            }
36            let mut on_stack = Vec::new();
37            detect_from(graph, start, &mut visited, &mut on_stack, &mut errs);
38        }
39        errs
40    }
41}
42
43/// DFS helper. Pushes node id onto `on_stack` on entry, pops on exit;
44/// a back-edge into `on_stack` is a cycle.
45fn detect_from(
46    graph: &PackGraph,
47    id: usize,
48    visited: &mut HashSet<usize>,
49    on_stack: &mut Vec<usize>,
50    errs: &mut Vec<PackValidationError>,
51) {
52    if on_stack.contains(&id) {
53        errs.push(build_cycle_error(graph, on_stack, id));
54        return;
55    }
56    if !visited.insert(id) {
57        return;
58    }
59    on_stack.push(id);
60    for edge in graph.edges() {
61        if edge.from == id && edge.kind == EdgeKind::Child {
62            detect_from(graph, edge.to, visited, on_stack, errs);
63        }
64    }
65    on_stack.pop();
66}
67
68/// Build a [`PackValidationError::GraphCycle`] whose chain lists the
69/// back-edge path.
70fn build_cycle_error(
71    graph: &PackGraph,
72    on_stack: &[usize],
73    back_edge_target: usize,
74) -> PackValidationError {
75    let mut chain: Vec<String> =
76        on_stack.iter().filter_map(|id| graph.node(*id).map(|n| n.name.clone())).collect();
77    if let Some(n) = graph.node(back_edge_target) {
78        chain.push(n.name.clone());
79    }
80    PackValidationError::GraphCycle { chain }
81}
grex_core/pack/validate/cycle.rs

grex_core/pack/validate/
cycle.rs
