haz_dag/
graph.rs

1//! [`TaskGraph`]: the validated task DAG of a workspace.
2//!
3//! A `TaskGraph` is the structural result of running construction
4//! over a fully-loaded workspace. It carries the set of nodes
5//! ([`TaskId`]s) and the set of [`Edge`]s tagged by kind. The
6//! single `edges` bag makes `DAG-014` cycle detection natural,
7//! since cycle detection operates on the *union* of hard, soft,
8//! and producer-matching edges; rules that target a single kind
9//! (hard-only topological order, weak-only conditional ordering)
10//! filter by [`EdgeKind`] cheaply.
11//!
12//! The data layer holds no construction-time invariants. Those
13//! belong to the graph-construction module.
14
15use std::collections::BTreeSet;
16
17use haz_domain::task_id::TaskId;
18
19use crate::edge::Edge;
20
21/// The validated task graph of a workspace.
22///
23/// # Examples
24///
25/// ```
26/// use std::collections::BTreeSet;
27/// use std::str::FromStr;
28/// use haz_dag::edge::{Edge, EdgeKind};
29/// use haz_dag::graph::TaskGraph;
30/// use haz_domain::name::{ProjectName, TaskName};
31/// use haz_domain::task_id::TaskId;
32///
33/// let a = TaskId {
34///     project: ProjectName::from_str("p").unwrap(),
35///     task: TaskName::from_str("a").unwrap(),
36/// };
37/// let b = TaskId {
38///     project: ProjectName::from_str("p").unwrap(),
39///     task: TaskName::from_str("b").unwrap(),
40/// };
41///
42/// let graph = TaskGraph {
43///     nodes: BTreeSet::from([a.clone(), b.clone()]),
44///     edges: BTreeSet::from([Edge {
45///         from: a,
46///         to: b,
47///         kind: EdgeKind::Hard,
48///     }]),
49/// };
50/// assert_eq!(graph.nodes.len(), 2);
51/// assert_eq!(graph.edges.len(), 1);
52/// ```
53#[derive(Debug, Clone, Default, PartialEq, Eq)]
54pub struct TaskGraph {
55    /// Every task that participates in the graph, by identity.
56    pub nodes: BTreeSet<TaskId>,
57    /// Every edge in the graph, tagged by [`crate::edge::EdgeKind`].
58    pub edges: BTreeSet<Edge>,
59}
60
61#[cfg(test)]
62mod tests {
63    use std::collections::BTreeSet;
64    use std::str::FromStr;
65
66    use haz_domain::name::{ProjectName, TaskName};
67    use haz_domain::task_id::TaskId;
68
69    use crate::edge::{Edge, EdgeKind};
70    use crate::graph::TaskGraph;
71
72    fn id(project: &str, task: &str) -> TaskId {
73        TaskId {
74            project: ProjectName::from_str(project).unwrap(),
75            task: TaskName::from_str(task).unwrap(),
76        }
77    }
78
79    fn edge(from: TaskId, to: TaskId, kind: EdgeKind) -> Edge {
80        Edge { from, to, kind }
81    }
82
83    #[test]
84    fn default_graph_is_empty() {
85        let graph = TaskGraph::default();
86        assert!(graph.nodes.is_empty());
87        assert!(graph.edges.is_empty());
88    }
89
90    #[test]
91    fn graph_with_isolated_nodes_no_edges() {
92        let graph = TaskGraph {
93            nodes: BTreeSet::from([id("p", "a"), id("p", "b"), id("q", "a")]),
94            edges: BTreeSet::new(),
95        };
96        assert_eq!(graph.nodes.len(), 3);
97        assert!(graph.edges.is_empty());
98    }
99
100    #[test]
101    fn graph_with_hard_chain_a_to_b_to_c() {
102        let a = id("p", "a");
103        let b = id("p", "b");
104        let c = id("p", "c");
105        let graph = TaskGraph {
106            nodes: BTreeSet::from([a.clone(), b.clone(), c.clone()]),
107            edges: BTreeSet::from([
108                edge(a.clone(), b.clone(), EdgeKind::Hard),
109                edge(b.clone(), c.clone(), EdgeKind::Hard),
110            ]),
111        };
112
113        assert_eq!(graph.nodes.len(), 3);
114        assert_eq!(graph.edges.len(), 2);
115
116        let hard: Vec<_> = graph
117            .edges
118            .iter()
119            .filter(|e| e.kind == EdgeKind::Hard)
120            .cloned()
121            .collect();
122        assert_eq!(hard.len(), 2);
123        assert!(hard.iter().any(|e| e.from == a && e.to == b));
124        assert!(hard.iter().any(|e| e.from == b && e.to == c));
125    }
126
127    #[test]
128    fn graph_admits_producer_matching_self_edge() {
129        // DAG-013: a formatter/auto-fixer task whose own outputs
130        // re-feed its own inputs gets a producer-matching self-edge.
131        let node = id("formatter", "format");
132        let graph = TaskGraph {
133            nodes: BTreeSet::from([node.clone()]),
134            edges: BTreeSet::from([edge(node.clone(), node.clone(), EdgeKind::ProducerMatching)]),
135        };
136        assert_eq!(graph.nodes.len(), 1);
137        assert_eq!(graph.edges.len(), 1);
138        let only = graph.edges.iter().next().unwrap();
139        assert_eq!(only.from, only.to);
140        assert_eq!(only.kind, EdgeKind::ProducerMatching);
141    }
142
143    #[test]
144    fn graph_clones_preserve_value() {
145        let a = id("p", "a");
146        let b = id("p", "b");
147        let original = TaskGraph {
148            nodes: BTreeSet::from([a.clone(), b.clone()]),
149            edges: BTreeSet::from([edge(a, b, EdgeKind::Soft)]),
150        };
151        let cloned = original.clone();
152        assert_eq!(original, cloned);
153    }
154}
haz_dag/graph.rs

haz_dag/
graph.rs
