haz-dag 0.1.0

DAG construction and traversal for haz tasks.
Documentation 
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

//! [`Edge`]: a directed relation between two [`TaskId`]s in the
//! task graph, tagged with its [`EdgeKind`].
//!
//! The three edge kinds correspond to the three relations defined
//! in `docs/spec/07-dag-semantics.md`:
//!
//! - [`EdgeKind::Hard`] (`DAG-008`): unconditional execution order
//!   from `deps`.
//! - [`EdgeKind::Soft`] (`DAG-009`): conditional execution order
//!   from `weakDeps`.
//! - [`EdgeKind::ProducerMatching`] (`DAG-013`): metadata relation
//!   between a producer's `outputs` and a consumer's `inputs`. Not
//!   itself an execution-order constraint; participates in cycle
//!   detection per `DAG-014`.
//!
//! All three kinds use the same direction convention: the edge
//! points from the predecessor (or producer) to the successor (or
//! consumer).
//!
//! The data layer enforces only structural invariants intrinsic to
//! the type. Construction-time validations (membership of `from`
//! and `to` in the graph's nodes, self-loop rejection for hard and
//! soft edges per `DAG-012`, deps/weakDeps mutual exclusion per
//! `DAG-010`) belong to the graph-construction module.

use std::fmt;

use haz_domain::task_id::TaskId;

/// The kind of relation an [`Edge`] represents.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum EdgeKind {
    /// A hard edge introduced by `deps` (`DAG-008`).
    Hard,
    /// A soft edge introduced by `weakDeps` (`DAG-009`).
    Soft,
    /// A producer-matching edge from an `outputs`/`inputs`
    /// intersection (`DAG-013`).
    ProducerMatching,
}

impl fmt::Display for EdgeKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let s = match self {
            EdgeKind::Hard => "hard",
            EdgeKind::Soft => "soft",
            EdgeKind::ProducerMatching => "producer-matching",
        };
        f.write_str(s)
    }
}

/// A directed edge in the task graph, tagged with its kind.
///
/// Sort order on `(from, to, kind)` lets a `BTreeSet<Edge>`
/// iterate in canonical order.
///
/// # Examples
///
/// ```
/// use std::str::FromStr;
/// use haz_dag::edge::{Edge, EdgeKind};
/// use haz_domain::name::{ProjectName, TaskName};
/// use haz_domain::task_id::TaskId;
///
/// let producer = TaskId {
///     project: ProjectName::from_str("lib_core").unwrap(),
///     task: TaskName::from_str("codegen").unwrap(),
/// };
/// let consumer = TaskId {
///     project: ProjectName::from_str("lib_core").unwrap(),
///     task: TaskName::from_str("build").unwrap(),
/// };
/// let edge = Edge {
///     from: producer,
///     to: consumer,
///     kind: EdgeKind::Hard,
/// };
/// assert_eq!(edge.to_string(), "lib_core:codegen -> lib_core:build (hard)");
/// ```
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Edge {
    /// The predecessor or producer endpoint.
    pub from: TaskId,
    /// The successor or consumer endpoint.
    pub to: TaskId,
    /// Which relation this edge represents.
    pub kind: EdgeKind,
}

impl fmt::Display for Edge {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{} -> {} ({})", self.from, self.to, self.kind)
    }
}

#[cfg(test)]
mod tests {
    use std::cmp::Ordering;
    use std::collections::BTreeSet;
    use std::str::FromStr;

    use haz_domain::name::{ProjectName, TaskName};
    use haz_domain::task_id::TaskId;

    use crate::edge::{Edge, EdgeKind};

    fn id(project: &str, task: &str) -> TaskId {
        TaskId {
            project: ProjectName::from_str(project).unwrap(),
            task: TaskName::from_str(task).unwrap(),
        }
    }

    fn edge(from: TaskId, to: TaskId, kind: EdgeKind) -> Edge {
        Edge { from, to, kind }
    }

    #[test]
    fn edge_kind_display() {
        assert_eq!(EdgeKind::Hard.to_string(), "hard");
        assert_eq!(EdgeKind::Soft.to_string(), "soft");
        assert_eq!(EdgeKind::ProducerMatching.to_string(), "producer-matching");
    }

    #[test]
    fn edge_display_renders_from_arrow_to_paren_kind() {
        let e = edge(id("a", "b"), id("c", "d"), EdgeKind::Hard);
        assert_eq!(e.to_string(), "a:b -> c:d (hard)");
    }

    #[test]
    fn edge_equality_is_structural() {
        let e1 = edge(id("a", "x"), id("b", "y"), EdgeKind::Hard);
        let e2 = edge(id("a", "x"), id("b", "y"), EdgeKind::Hard);
        let e3 = edge(id("a", "x"), id("b", "y"), EdgeKind::Soft);
        let e4 = edge(id("a", "x"), id("b", "z"), EdgeKind::Hard);
        assert_eq!(e1, e2);
        assert_ne!(e1, e3, "different kind => different edge");
        assert_ne!(e1, e4, "different endpoints => different edge");
    }

    #[test]
    fn edge_ord_is_from_then_to_then_kind() {
        let lower_from = edge(id("a", "z"), id("z", "z"), EdgeKind::Hard);
        let higher_from = edge(id("b", "a"), id("a", "a"), EdgeKind::Hard);
        assert_eq!(
            lower_from.cmp(&higher_from),
            Ordering::Less,
            "from decides first"
        );

        let lower_to = edge(id("a", "a"), id("a", "x"), EdgeKind::Hard);
        let higher_to = edge(id("a", "a"), id("a", "y"), EdgeKind::Hard);
        assert_eq!(lower_to.cmp(&higher_to), Ordering::Less, "to decides next");

        let hard = edge(id("a", "a"), id("b", "b"), EdgeKind::Hard);
        let soft = edge(id("a", "a"), id("b", "b"), EdgeKind::Soft);
        let producer = edge(id("a", "a"), id("b", "b"), EdgeKind::ProducerMatching);
        assert_eq!(hard.cmp(&soft), Ordering::Less);
        assert_eq!(soft.cmp(&producer), Ordering::Less);
    }

    #[test]
    fn self_edge_is_representable_for_producer_matching() {
        // DAG-013: a task whose `inputs` and `outputs` patterns
        // intersect is its own producer; the data layer admits
        // this self-edge.
        let node = id("formatter", "format");
        let self_edge = edge(node.clone(), node, EdgeKind::ProducerMatching);
        assert_eq!(self_edge.from, self_edge.to);
    }

    #[test]
    fn self_edge_is_representable_for_hard_and_soft_too() {
        // The data layer does not enforce DAG-012 (self-reference
        // rejection in deps and weakDeps); construction does.
        let node = id("p", "t");
        let _ = edge(node.clone(), node.clone(), EdgeKind::Hard);
        let _ = edge(node.clone(), node, EdgeKind::Soft);
    }

    #[test]
    fn btreeset_iterates_in_canonical_order() {
        let mut set = BTreeSet::new();
        set.insert(edge(id("b", "y"), id("c", "z"), EdgeKind::Hard));
        set.insert(edge(id("a", "x"), id("b", "y"), EdgeKind::Hard));
        set.insert(edge(id("a", "x"), id("b", "y"), EdgeKind::Soft));
        set.insert(edge(id("a", "x"), id("b", "y"), EdgeKind::ProducerMatching));

        let collected: Vec<_> = set.iter().map(ToString::to_string).collect();
        assert_eq!(
            collected,
            vec![
                "a:x -> b:y (hard)",
                "a:x -> b:y (soft)",
                "a:x -> b:y (producer-matching)",
                "b:y -> c:z (hard)",
            ],
        );
    }

    #[test]
    fn clone_preserves_value() {
        let original = edge(id("a", "b"), id("c", "d"), EdgeKind::Soft);
        let cloned = original.clone();
        assert_eq!(original, cloned);
    }
}