batty_cli/team/
deps.rs

1//! Dependency graph visualization for board tasks.
2
3use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
4use std::fmt::Write as _;
5use std::path::Path;
6
7use anyhow::{Result, bail};
8
9use crate::task::{Task, load_tasks_from_dir};
10
11/// Output format for dependency graph.
12#[derive(Debug, Clone, Copy, PartialEq, Eq)]
13pub enum DepsFormat {
14    Tree,
15    Flat,
16    Dot,
17}
18
19/// A node in the dependency graph.
20#[derive(Debug)]
21struct TaskNode {
22    id: u32,
23    title: String,
24    status: String,
25    priority: String,
26    depends_on: Vec<u32>,
27}
28
29impl TaskNode {
30    fn from_task(task: &Task) -> Self {
31        Self {
32            id: task.id,
33            title: task.title.clone(),
34            status: task.status.clone(),
35            priority: task.priority.clone(),
36            depends_on: task.depends_on.clone(),
37        }
38    }
39
40    fn truncated_title(&self, max_len: usize) -> String {
41        if self.title.len() <= max_len {
42            self.title.clone()
43        } else {
44            format!("{}...", &self.title[..max_len - 3])
45        }
46    }
47
48    fn status_indicator(&self) -> &str {
49        match self.status.as_str() {
50            "done" => "[x]",
51            "in-progress" => "[>]",
52            "review" => "[R]",
53            "todo" => "[ ]",
54            "backlog" => "[-]",
55            "blocked" => "[!]",
56            _ => "[?]",
57        }
58    }
59
60    fn is_incomplete(&self) -> bool {
61        self.status != "done"
62    }
63}
64
65/// Build and render the dependency graph.
66pub fn render_deps(board_dir: &Path, format: DepsFormat) -> Result<String> {
67    let tasks_dir = board_dir.join("tasks");
68    if !tasks_dir.is_dir() {
69        bail!("no tasks directory found at {}", tasks_dir.display());
70    }
71
72    let tasks = load_tasks_from_dir(&tasks_dir)?;
73    let nodes: BTreeMap<u32, TaskNode> = tasks
74        .iter()
75        .map(|t| (t.id, TaskNode::from_task(t)))
76        .collect();
77
78    // Check for cycles before rendering
79    if let Some(cycle) = detect_cycle(&nodes) {
80        let cycle_str = cycle
81            .iter()
82            .map(|id| format!("#{id}"))
83            .collect::<Vec<_>>()
84            .join(" -> ");
85        bail!("dependency cycle detected: {cycle_str}");
86    }
87
88    match format {
89        DepsFormat::Tree => render_tree(&nodes),
90        DepsFormat::Flat => render_flat(&nodes),
91        DepsFormat::Dot => render_dot(&nodes),
92    }
93}
94
95/// Detect cycles using DFS. Returns the cycle path if found.
96fn detect_cycle(nodes: &BTreeMap<u32, TaskNode>) -> Option<Vec<u32>> {
97    let mut visited = HashSet::new();
98    let mut in_stack = HashSet::new();
99    let mut path = Vec::new();
100
101    for &id in nodes.keys() {
102        if !visited.contains(&id) {
103            if let Some(cycle) = dfs_cycle(id, nodes, &mut visited, &mut in_stack, &mut path) {
104                return Some(cycle);
105            }
106        }
107    }
108    None
109}
110
111fn dfs_cycle(
112    id: u32,
113    nodes: &BTreeMap<u32, TaskNode>,
114    visited: &mut HashSet<u32>,
115    in_stack: &mut HashSet<u32>,
116    path: &mut Vec<u32>,
117) -> Option<Vec<u32>> {
118    visited.insert(id);
119    in_stack.insert(id);
120    path.push(id);
121
122    if let Some(node) = nodes.get(&id) {
123        for &dep in &node.depends_on {
124            if !nodes.contains_key(&dep) {
125                continue; // skip references to non-existent tasks
126            }
127            if in_stack.contains(&dep) {
128                // Found a cycle — extract it
129                let cycle_start = path.iter().position(|&x| x == dep).unwrap();
130                let mut cycle = path[cycle_start..].to_vec();
131                cycle.push(dep);
132                return Some(cycle);
133            }
134            if !visited.contains(&dep) {
135                if let Some(cycle) = dfs_cycle(dep, nodes, visited, in_stack, path) {
136                    return Some(cycle);
137                }
138            }
139        }
140    }
141
142    path.pop();
143    in_stack.remove(&id);
144    None
145}
146
147/// Render tree format: roots at top, children indented below.
148fn render_tree(nodes: &BTreeMap<u32, TaskNode>) -> Result<String> {
149    // Build reverse map: parent -> children (tasks that depend on parent)
150    let mut children: BTreeMap<u32, BTreeSet<u32>> = BTreeMap::new();
151    let mut has_parent = HashSet::new();
152
153    for node in nodes.values() {
154        for &dep in &node.depends_on {
155            if nodes.contains_key(&dep) {
156                children.entry(dep).or_default().insert(node.id);
157                has_parent.insert(node.id);
158            }
159        }
160    }
161
162    // Roots are tasks with no dependencies (or deps pointing to non-existent tasks)
163    let roots: Vec<u32> = nodes
164        .keys()
165        .filter(|id| !has_parent.contains(id))
166        .copied()
167        .collect();
168
169    if roots.is_empty() && !nodes.is_empty() {
170        // All tasks have parents — shouldn't happen without cycles
171        return Ok("(no root tasks found)\n".to_string());
172    }
173
174    let mut out = String::new();
175
176    // Show blocked chains header
177    let blocked = find_blocked_chains(nodes);
178    if !blocked.is_empty() {
179        writeln!(out, "Blocked chains:").unwrap();
180        for chain in &blocked {
181            let parts: Vec<String> = chain
182                .iter()
183                .map(|&id| {
184                    let node = &nodes[&id];
185                    format!("#{} {}", id, node.truncated_title(30))
186                })
187                .collect();
188            writeln!(out, "  {} (waiting)", parts.join(" -> ")).unwrap();
189        }
190        writeln!(out).unwrap();
191    }
192
193    // Show critical path
194    let critical = find_critical_path(nodes);
195    if critical.len() > 1 {
196        let parts: Vec<String> = critical.iter().map(|&id| format!("#{id}")).collect();
197        writeln!(
198            out,
199            "Critical path ({}): {}",
200            critical.len(),
201            parts.join(" -> ")
202        )
203        .unwrap();
204        writeln!(out).unwrap();
205    }
206
207    // Render tree
208    writeln!(out, "Dependency tree:").unwrap();
209    for &root in &roots {
210        render_tree_node(root, nodes, &children, &mut out, "", true);
211    }
212
213    Ok(out)
214}
215
216fn render_tree_node(
217    id: u32,
218    nodes: &BTreeMap<u32, TaskNode>,
219    children: &BTreeMap<u32, BTreeSet<u32>>,
220    out: &mut String,
221    prefix: &str,
222    is_last: bool,
223) {
224    let Some(node) = nodes.get(&id) else { return };
225
226    let connector = if prefix.is_empty() {
227        ""
228    } else if is_last {
229        "└── "
230    } else {
231        "├── "
232    };
233
234    let priority_tag = if node.priority.is_empty() {
235        String::new()
236    } else {
237        format!(" ({})", node.priority)
238    };
239
240    writeln!(
241        out,
242        "{prefix}{connector}{} #{} {}{}",
243        node.status_indicator(),
244        node.id,
245        node.truncated_title(50),
246        priority_tag,
247    )
248    .unwrap();
249
250    let child_ids: Vec<u32> = children
251        .get(&id)
252        .map(|s| s.iter().copied().collect())
253        .unwrap_or_default();
254
255    let child_prefix = if prefix.is_empty() {
256        String::new()
257    } else if is_last {
258        format!("{prefix}    ")
259    } else {
260        format!("{prefix}│   ")
261    };
262
263    for (i, &child) in child_ids.iter().enumerate() {
264        let child_is_last = i == child_ids.len() - 1;
265        render_tree_node(child, nodes, children, out, &child_prefix, child_is_last);
266    }
267}
268
269/// Render flat format: just dependency pairs.
270fn render_flat(nodes: &BTreeMap<u32, TaskNode>) -> Result<String> {
271    let mut out = String::new();
272    let mut has_deps = false;
273
274    for node in nodes.values() {
275        for &dep in &node.depends_on {
276            if nodes.contains_key(&dep) {
277                writeln!(out, "#{} -> #{}", node.id, dep).unwrap();
278                has_deps = true;
279            }
280        }
281    }
282
283    if !has_deps {
284        writeln!(out, "(no dependencies)").unwrap();
285    }
286    Ok(out)
287}
288
289/// Render graphviz DOT format.
290fn render_dot(nodes: &BTreeMap<u32, TaskNode>) -> Result<String> {
291    let mut out = String::new();
292    writeln!(out, "digraph deps {{").unwrap();
293    writeln!(out, "  rankdir=BT;").unwrap();
294    writeln!(out, "  node [shape=box];").unwrap();
295
296    for node in nodes.values() {
297        if node.depends_on.is_empty() && !nodes.values().any(|n| n.depends_on.contains(&node.id)) {
298            continue; // skip isolated nodes
299        }
300
301        let color = match node.status.as_str() {
302            "done" => "green",
303            "in-progress" => "yellow",
304            "review" => "orange",
305            "todo" | "backlog" => "white",
306            _ => "gray",
307        };
308
309        writeln!(
310            out,
311            "  t{} [label=\"#{} {}\" style=filled fillcolor={}];",
312            node.id,
313            node.id,
314            node.truncated_title(30).replace('"', "\\\""),
315            color,
316        )
317        .unwrap();
318    }
319
320    writeln!(out).unwrap();
321
322    for node in nodes.values() {
323        for &dep in &node.depends_on {
324            if nodes.contains_key(&dep) {
325                writeln!(out, "  t{} -> t{};", node.id, dep).unwrap();
326            }
327        }
328    }
329
330    writeln!(out, "}}").unwrap();
331    Ok(out)
332}
333
334/// Find chains where an incomplete task is blocked on another incomplete task.
335fn find_blocked_chains(nodes: &BTreeMap<u32, TaskNode>) -> Vec<Vec<u32>> {
336    let mut chains = Vec::new();
337
338    for node in nodes.values() {
339        if !node.is_incomplete() {
340            continue;
341        }
342        for &dep in &node.depends_on {
343            if let Some(dep_node) = nodes.get(&dep) {
344                if dep_node.is_incomplete() {
345                    chains.push(vec![node.id, dep]);
346                }
347            }
348        }
349    }
350
351    chains.sort();
352    chains
353}
354
355/// Find the longest chain of incomplete tasks (critical path).
356fn find_critical_path(nodes: &BTreeMap<u32, TaskNode>) -> Vec<u32> {
357    let mut memo: HashMap<u32, Vec<u32>> = HashMap::new();
358    let mut best = Vec::new();
359
360    for &id in nodes.keys() {
361        let path = longest_path(id, nodes, &mut memo);
362        if path.len() > best.len() {
363            best = path;
364        }
365    }
366
367    best
368}
369
370fn longest_path(
371    id: u32,
372    nodes: &BTreeMap<u32, TaskNode>,
373    memo: &mut HashMap<u32, Vec<u32>>,
374) -> Vec<u32> {
375    if let Some(cached) = memo.get(&id) {
376        return cached.clone();
377    }
378
379    let Some(node) = nodes.get(&id) else {
380        return Vec::new();
381    };
382
383    if !node.is_incomplete() {
384        memo.insert(id, Vec::new());
385        return Vec::new();
386    }
387
388    let mut best_child = Vec::new();
389    for &dep in &node.depends_on {
390        if nodes.contains_key(&dep) {
391            let child_path = longest_path(dep, nodes, memo);
392            if child_path.len() > best_child.len() {
393                best_child = child_path;
394            }
395        }
396    }
397
398    let mut path = vec![id];
399    path.extend(best_child);
400    memo.insert(id, path.clone());
401    path
402}
403
404#[cfg(test)]
405mod tests {
406    use super::*;
407    use std::fs;
408    use tempfile::TempDir;
409
410    fn write_task(
411        dir: &Path,
412        id: u32,
413        title: &str,
414        status: &str,
415        priority: &str,
416        depends_on: &[u32],
417    ) {
418        let deps = if depends_on.is_empty() {
419            "depends_on: []".to_string()
420        } else {
421            let items: Vec<String> = depends_on.iter().map(|d| format!("  - {d}")).collect();
422            format!("depends_on:\n{}", items.join("\n"))
423        };
424        let content = format!(
425            "---\nid: {id}\ntitle: {title}\nstatus: {status}\npriority: {priority}\n{deps}\nclass: standard\n---\n\nDescription.\n"
426        );
427        fs::write(dir.join(format!("{id:03}-task.md")), content).unwrap();
428    }
429
430    fn setup_board(tasks: &[(u32, &str, &str, &str, &[u32])]) -> TempDir {
431        let tmp = TempDir::new().unwrap();
432        let tasks_dir = tmp.path().join("tasks");
433        fs::create_dir_all(&tasks_dir).unwrap();
434        for &(id, title, status, priority, deps) in tasks {
435            write_task(&tasks_dir, id, title, status, priority, deps);
436        }
437        tmp
438    }
439
440    #[test]
441    fn empty_board() {
442        let tmp = TempDir::new().unwrap();
443        let tasks_dir = tmp.path().join("tasks");
444        fs::create_dir_all(&tasks_dir).unwrap();
445
446        let output = render_deps(tmp.path(), DepsFormat::Tree).unwrap();
447        assert!(output.contains("Dependency tree:"));
448
449        let flat = render_deps(tmp.path(), DepsFormat::Flat).unwrap();
450        assert!(flat.contains("(no dependencies)"));
451    }
452
453    #[test]
454    fn no_dependencies() {
455        let tmp = setup_board(&[
456            (1, "Task A", "todo", "high", &[]),
457            (2, "Task B", "todo", "medium", &[]),
458        ]);
459
460        let flat = render_deps(tmp.path(), DepsFormat::Flat).unwrap();
461        assert!(flat.contains("(no dependencies)"));
462
463        let tree = render_deps(tmp.path(), DepsFormat::Tree).unwrap();
464        assert!(tree.contains("#1"));
465        assert!(tree.contains("#2"));
466    }
467
468    #[test]
469    fn linear_chain() {
470        let tmp = setup_board(&[
471            (1, "Foundation", "done", "high", &[]),
472            (2, "Build on foundation", "in-progress", "high", &[1]),
473            (3, "Final step", "todo", "medium", &[2]),
474        ]);
475
476        let tree = render_deps(tmp.path(), DepsFormat::Tree).unwrap();
477        assert!(tree.contains("#1"));
478        assert!(tree.contains("#2"));
479        assert!(tree.contains("#3"));
480        assert!(tree.contains("Foundation"));
481
482        let flat = render_deps(tmp.path(), DepsFormat::Flat).unwrap();
483        assert!(flat.contains("#2 -> #1"));
484        assert!(flat.contains("#3 -> #2"));
485    }
486
487    #[test]
488    fn diamond_dependencies() {
489        let tmp = setup_board(&[
490            (1, "Root", "done", "high", &[]),
491            (2, "Left", "todo", "medium", &[1]),
492            (3, "Right", "todo", "medium", &[1]),
493            (4, "Join", "todo", "low", &[2, 3]),
494        ]);
495
496        let flat = render_deps(tmp.path(), DepsFormat::Flat).unwrap();
497        assert!(flat.contains("#2 -> #1"));
498        assert!(flat.contains("#3 -> #1"));
499        assert!(flat.contains("#4 -> #2"));
500        assert!(flat.contains("#4 -> #3"));
501    }
502
503    #[test]
504    fn cycle_detection() {
505        let tmp = setup_board(&[
506            (1, "Task A", "todo", "high", &[2]),
507            (2, "Task B", "todo", "high", &[1]),
508        ]);
509
510        let result = render_deps(tmp.path(), DepsFormat::Tree);
511        assert!(result.is_err());
512        let err = result.unwrap_err().to_string();
513        assert!(err.contains("cycle"));
514    }
515
516    #[test]
517    fn blocked_chains_shown() {
518        let tmp = setup_board(&[
519            (1, "Blocker", "todo", "high", &[]),
520            (2, "Blocked task", "todo", "medium", &[1]),
521        ]);
522
523        let tree = render_deps(tmp.path(), DepsFormat::Tree).unwrap();
524        assert!(tree.contains("Blocked chains:"));
525        assert!(tree.contains("#2"));
526        assert!(tree.contains("#1"));
527    }
528
529    #[test]
530    fn done_deps_not_blocked() {
531        let tmp = setup_board(&[
532            (1, "Done task", "done", "high", &[]),
533            (2, "Ready task", "todo", "medium", &[1]),
534        ]);
535
536        let tree = render_deps(tmp.path(), DepsFormat::Tree).unwrap();
537        assert!(!tree.contains("Blocked chains:"));
538    }
539
540    #[test]
541    fn critical_path_shown() {
542        let tmp = setup_board(&[
543            (1, "Step 1", "todo", "high", &[]),
544            (2, "Step 2", "todo", "high", &[1]),
545            (3, "Step 3", "todo", "high", &[2]),
546        ]);
547
548        let tree = render_deps(tmp.path(), DepsFormat::Tree).unwrap();
549        assert!(tree.contains("Critical path (3)"));
550        assert!(tree.contains("#3 -> #2 -> #1"));
551    }
552
553    #[test]
554    fn dot_format() {
555        let tmp = setup_board(&[
556            (1, "Root", "done", "high", &[]),
557            (2, "Child", "todo", "medium", &[1]),
558        ]);
559
560        let dot = render_deps(tmp.path(), DepsFormat::Dot).unwrap();
561        assert!(dot.contains("digraph deps {"));
562        assert!(dot.contains("t2 -> t1;"));
563        assert!(dot.contains("fillcolor=green"));
564        assert!(dot.contains("fillcolor=white"));
565        assert!(dot.contains("}"));
566    }
567
568    #[test]
569    fn title_truncation() {
570        let node = TaskNode {
571            id: 1,
572            title: "A very long task title that should be truncated to fit within limits"
573                .to_string(),
574            status: "todo".to_string(),
575            priority: "high".to_string(),
576            depends_on: vec![],
577        };
578        let truncated = node.truncated_title(50);
579        assert!(truncated.len() <= 50);
580        assert!(truncated.ends_with("..."));
581    }
582
583    #[test]
584    fn status_indicators() {
585        let statuses = vec![
586            ("done", "[x]"),
587            ("in-progress", "[>]"),
588            ("review", "[R]"),
589            ("todo", "[ ]"),
590            ("backlog", "[-]"),
591            ("blocked", "[!]"),
592            ("unknown", "[?]"),
593        ];
594
595        for (status, expected) in statuses {
596            let node = TaskNode {
597                id: 1,
598                title: "Test".to_string(),
599                status: status.to_string(),
600                priority: "".to_string(),
601                depends_on: vec![],
602            };
603            assert_eq!(node.status_indicator(), expected, "status={status}");
604        }
605    }
606
607    #[test]
608    fn missing_tasks_dir_errors() {
609        let tmp = TempDir::new().unwrap();
610        let result = render_deps(tmp.path(), DepsFormat::Tree);
611        assert!(result.is_err());
612        assert!(
613            result
614                .unwrap_err()
615                .to_string()
616                .contains("no tasks directory")
617        );
618    }
619
620    #[test]
621    fn deps_to_nonexistent_tasks_ignored() {
622        let tmp = setup_board(&[(1, "Task", "todo", "high", &[999])]);
623
624        // Should not error — just skip the nonexistent dep
625        let flat = render_deps(tmp.path(), DepsFormat::Flat).unwrap();
626        assert!(flat.contains("(no dependencies)"));
627    }
628
629    #[test]
630    fn three_node_cycle_detected() {
631        let tmp = setup_board(&[
632            (1, "A", "todo", "high", &[3]),
633            (2, "B", "todo", "high", &[1]),
634            (3, "C", "todo", "high", &[2]),
635        ]);
636
637        let result = render_deps(tmp.path(), DepsFormat::Flat);
638        assert!(result.is_err());
639        assert!(result.unwrap_err().to_string().contains("cycle"));
640    }
641}
batty_cli/team/deps.rs

batty_cli/team/
deps.rs
