oximedia_workflow/
task_dependency.rs

1//! Task dependency modelling for `oximedia-workflow`.
2//!
3//! Provides [`DependencyKind`] classification, [`TaskDependency`] edges, and a
4//! [`DependencyResolver`] that performs a topological sort to determine correct
5//! execution order and parallelism opportunities.
6
7#![allow(dead_code)]
8
9use serde::{Deserialize, Serialize};
10use std::collections::{HashMap, HashSet, VecDeque};
11
12// ---------------------------------------------------------------------------
13// Dependency kind
14// ---------------------------------------------------------------------------
15
16/// Nature of the relationship between a predecessor and a successor task.
17#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
18pub enum DependencyKind {
19    /// Successor cannot start until predecessor finishes successfully.
20    FinishToStart,
21    /// Successor cannot start until predecessor starts.
22    StartToStart,
23    /// Successor cannot finish until predecessor finishes.
24    FinishToFinish,
25    /// Soft dependency: preferred but not enforced (hints for the scheduler).
26    Preferred,
27}
28
29impl DependencyKind {
30    /// Returns a short label.
31    #[must_use]
32    pub const fn label(self) -> &'static str {
33        match self {
34            Self::FinishToStart => "Finish-to-Start",
35            Self::StartToStart => "Start-to-Start",
36            Self::FinishToFinish => "Finish-to-Finish",
37            Self::Preferred => "Preferred",
38        }
39    }
40
41    /// Returns all variants.
42    #[must_use]
43    pub const fn all() -> &'static [DependencyKind] {
44        &[
45            Self::FinishToStart,
46            Self::StartToStart,
47            Self::FinishToFinish,
48            Self::Preferred,
49        ]
50    }
51
52    /// Returns `true` if this dependency kind is strictly enforced.
53    #[must_use]
54    pub const fn is_hard(self) -> bool {
55        !matches!(self, Self::Preferred)
56    }
57}
58
59impl std::fmt::Display for DependencyKind {
60    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
61        f.write_str(self.label())
62    }
63}
64
65// ---------------------------------------------------------------------------
66// Task dependency edge
67// ---------------------------------------------------------------------------
68
69/// A directed edge from one task to another in a dependency graph.
70#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
71pub struct TaskDependency {
72    /// Task that must complete (or start) first.
73    pub from: String,
74    /// Task that depends on `from`.
75    pub to: String,
76    /// Nature of the dependency.
77    pub kind: DependencyKind,
78}
79
80impl TaskDependency {
81    /// Creates a new dependency edge.
82    #[must_use]
83    pub fn new(from: impl Into<String>, to: impl Into<String>, kind: DependencyKind) -> Self {
84        Self {
85            from: from.into(),
86            to: to.into(),
87            kind,
88        }
89    }
90
91    /// Convenience constructor for the most common Finish-to-Start edge.
92    #[must_use]
93    pub fn finish_to_start(from: impl Into<String>, to: impl Into<String>) -> Self {
94        Self::new(from, to, DependencyKind::FinishToStart)
95    }
96}
97
98// ---------------------------------------------------------------------------
99// Dependency resolver
100// ---------------------------------------------------------------------------
101
102/// Resolves a set of [`TaskDependency`] edges into a topologically-sorted
103/// execution order, detecting cycles.
104#[derive(Debug, Clone, Default)]
105pub struct DependencyResolver {
106    edges: Vec<TaskDependency>,
107}
108
109impl DependencyResolver {
110    /// Creates a new empty resolver.
111    #[must_use]
112    pub fn new() -> Self {
113        Self { edges: Vec::new() }
114    }
115
116    /// Adds a dependency edge.
117    pub fn add(&mut self, dep: TaskDependency) {
118        self.edges.push(dep);
119    }
120
121    /// Returns the number of edges.
122    #[must_use]
123    pub fn edge_count(&self) -> usize {
124        self.edges.len()
125    }
126
127    /// Returns all registered edges.
128    #[must_use]
129    pub fn edges(&self) -> &[TaskDependency] {
130        &self.edges
131    }
132
133    /// Collects the set of all task IDs referenced in the edges.
134    #[must_use]
135    pub fn all_tasks(&self) -> HashSet<String> {
136        let mut set = HashSet::new();
137        for e in &self.edges {
138            set.insert(e.from.clone());
139            set.insert(e.to.clone());
140        }
141        set
142    }
143
144    /// Returns the direct predecessors (hard deps only) of a given task.
145    #[must_use]
146    pub fn predecessors(&self, task_id: &str) -> Vec<String> {
147        self.edges
148            .iter()
149            .filter(|e| e.to == task_id && e.kind.is_hard())
150            .map(|e| e.from.clone())
151            .collect()
152    }
153
154    /// Returns the direct successors (hard deps only) of a given task.
155    #[must_use]
156    pub fn successors(&self, task_id: &str) -> Vec<String> {
157        self.edges
158            .iter()
159            .filter(|e| e.from == task_id && e.kind.is_hard())
160            .map(|e| e.to.clone())
161            .collect()
162    }
163
164    /// Performs a Kahn-style topological sort on hard dependencies.
165    ///
166    /// Returns `Ok(order)` if the graph is a DAG, or `Err(())` if a cycle
167    /// is detected.
168    pub fn topological_sort(&self) -> std::result::Result<Vec<String>, ()> {
169        // Build adjacency and in-degree maps (hard edges only).
170        let tasks = self.all_tasks();
171        let mut in_degree: HashMap<String, usize> = tasks.iter().map(|t| (t.clone(), 0)).collect();
172        let mut adj: HashMap<String, Vec<String>> =
173            tasks.iter().map(|t| (t.clone(), Vec::new())).collect();
174
175        for e in &self.edges {
176            if e.kind.is_hard() {
177                adj.get_mut(&e.from)
178                    .expect("should succeed in test")
179                    .push(e.to.clone());
180                *in_degree.get_mut(&e.to).expect("should succeed in test") += 1;
181            }
182        }
183
184        let mut queue: VecDeque<String> = in_degree
185            .iter()
186            .filter(|(_, &d)| d == 0)
187            .map(|(t, _)| t.clone())
188            .collect();
189        // Sort for deterministic output in tests.
190        let mut q_sorted: Vec<String> = queue.drain(..).collect();
191        q_sorted.sort();
192        for t in q_sorted {
193            queue.push_back(t);
194        }
195
196        let mut order = Vec::new();
197        while let Some(task) = queue.pop_front() {
198            order.push(task.clone());
199            let mut next_batch = Vec::new();
200            for succ in adj.get(&task).expect("should succeed in test") {
201                let d = in_degree.get_mut(succ).expect("should succeed in test");
202                *d -= 1;
203                if *d == 0 {
204                    next_batch.push(succ.clone());
205                }
206            }
207            next_batch.sort();
208            for t in next_batch {
209                queue.push_back(t);
210            }
211        }
212
213        if order.len() == tasks.len() {
214            Ok(order)
215        } else {
216            Err(())
217        }
218    }
219
220    /// Clears all edges.
221    pub fn clear(&mut self) {
222        self.edges.clear();
223    }
224}
225
226// ===========================================================================
227// Tests
228// ===========================================================================
229
230#[cfg(test)]
231mod tests {
232    use super::*;
233
234    // -- DependencyKind -----------------------------------------------------
235
236    #[test]
237    fn test_kind_label() {
238        assert_eq!(DependencyKind::FinishToStart.label(), "Finish-to-Start");
239        assert_eq!(DependencyKind::Preferred.label(), "Preferred");
240    }
241
242    #[test]
243    fn test_kind_display() {
244        assert_eq!(
245            format!("{}", DependencyKind::StartToStart),
246            "Start-to-Start"
247        );
248    }
249
250    #[test]
251    fn test_kind_all() {
252        assert_eq!(DependencyKind::all().len(), 4);
253    }
254
255    #[test]
256    fn test_kind_is_hard() {
257        assert!(DependencyKind::FinishToStart.is_hard());
258        assert!(!DependencyKind::Preferred.is_hard());
259    }
260
261    // -- TaskDependency -----------------------------------------------------
262
263    #[test]
264    fn test_dependency_new() {
265        let d = TaskDependency::new("a", "b", DependencyKind::FinishToStart);
266        assert_eq!(d.from, "a");
267        assert_eq!(d.to, "b");
268    }
269
270    #[test]
271    fn test_dependency_finish_to_start() {
272        let d = TaskDependency::finish_to_start("x", "y");
273        assert_eq!(d.kind, DependencyKind::FinishToStart);
274    }
275
276    // -- DependencyResolver -------------------------------------------------
277
278    #[test]
279    fn test_resolver_empty() {
280        let r = DependencyResolver::new();
281        assert_eq!(r.edge_count(), 0);
282        assert!(r.all_tasks().is_empty());
283    }
284
285    #[test]
286    fn test_resolver_add() {
287        let mut r = DependencyResolver::new();
288        r.add(TaskDependency::finish_to_start("a", "b"));
289        assert_eq!(r.edge_count(), 1);
290        assert_eq!(r.all_tasks().len(), 2);
291    }
292
293    #[test]
294    fn test_predecessors() {
295        let mut r = DependencyResolver::new();
296        r.add(TaskDependency::finish_to_start("a", "c"));
297        r.add(TaskDependency::finish_to_start("b", "c"));
298        let preds = r.predecessors("c");
299        assert_eq!(preds.len(), 2);
300        assert!(preds.contains(&"a".to_string()));
301        assert!(preds.contains(&"b".to_string()));
302    }
303
304    #[test]
305    fn test_successors() {
306        let mut r = DependencyResolver::new();
307        r.add(TaskDependency::finish_to_start("a", "b"));
308        r.add(TaskDependency::finish_to_start("a", "c"));
309        let succs = r.successors("a");
310        assert_eq!(succs.len(), 2);
311    }
312
313    #[test]
314    fn test_topological_sort_linear() {
315        let mut r = DependencyResolver::new();
316        r.add(TaskDependency::finish_to_start("a", "b"));
317        r.add(TaskDependency::finish_to_start("b", "c"));
318        let order = r.topological_sort().expect("should succeed in test");
319        assert_eq!(order, vec!["a", "b", "c"]);
320    }
321
322    #[test]
323    fn test_topological_sort_diamond() {
324        let mut r = DependencyResolver::new();
325        r.add(TaskDependency::finish_to_start("a", "b"));
326        r.add(TaskDependency::finish_to_start("a", "c"));
327        r.add(TaskDependency::finish_to_start("b", "d"));
328        r.add(TaskDependency::finish_to_start("c", "d"));
329        let order = r.topological_sort().expect("should succeed in test");
330        assert_eq!(order[0], "a");
331        assert_eq!(order[3], "d");
332    }
333
334    #[test]
335    fn test_topological_sort_cycle() {
336        let mut r = DependencyResolver::new();
337        r.add(TaskDependency::finish_to_start("a", "b"));
338        r.add(TaskDependency::finish_to_start("b", "a"));
339        assert!(r.topological_sort().is_err());
340    }
341
342    #[test]
343    fn test_preferred_edges_ignored_in_sort() {
344        let mut r = DependencyResolver::new();
345        r.add(TaskDependency::finish_to_start("a", "b"));
346        // Preferred edge b->a would cause a cycle if treated as hard.
347        r.add(TaskDependency::new("b", "a", DependencyKind::Preferred));
348        let order = r.topological_sort().expect("should succeed in test");
349        assert_eq!(order, vec!["a", "b"]);
350    }
351
352    #[test]
353    fn test_clear() {
354        let mut r = DependencyResolver::new();
355        r.add(TaskDependency::finish_to_start("a", "b"));
356        r.clear();
357        assert_eq!(r.edge_count(), 0);
358    }
359}
oximedia_workflow/task_dependency.rs

oximedia_workflow/
task_dependency.rs
