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

batty_cli/team/
deps.rs
