Skip to main content

orch/cli/
tree.rs

1//! Task tree visualization — ASCII tree view of parent-child relationships.
2
3use crate::backends::ExternalTask;
4use crate::engine::tasks::Task;
5use crate::store;
6use std::collections::HashMap;
7use std::fmt::Write as _;
8
9/// A node in the task tree.
10#[derive(Debug, Clone)]
11pub struct TreeNode {
12    pub id: String,
13    pub title: String,
14    pub status: String,
15    pub agent: Option<String>,
16    pub children: Vec<TreeNode>,
17}
18
19impl TreeNode {
20    /// Create a new tree node from an external task.
21    pub fn from_external(task: &ExternalTask) -> Self {
22        let status = task
23            .labels
24            .iter()
25            .find(|l| l.starts_with("status:"))
26            .map_or_else(|| "unknown".to_string(), |s| s.replace("status:", ""));
27
28        let agent = task
29            .labels
30            .iter()
31            .find(|l| l.starts_with("agent:"))
32            .map(|s| s.replace("agent:", ""));
33
34        Self {
35            id: task.id.0.clone(),
36            title: task.title.clone(),
37            status,
38            agent,
39            children: Vec::new(),
40        }
41    }
42
43    /// Create a tree node for an internal task (from store).
44    pub fn from_internal(task: &store::Task) -> Self {
45        Self {
46            id: task
47                .external_id
48                .clone()
49                .unwrap_or_else(|| task.id.to_string()),
50            title: task.title.clone(),
51            status: task.status.as_str().to_string(),
52            agent: task.agent.clone(),
53            children: Vec::new(),
54        }
55    }
56}
57
58/// Order nodes by numeric ID, with non-numeric IDs counting as 0.
59fn sort_by_numeric_id(nodes: &mut [TreeNode]) {
60    nodes.sort_by_key(|n| n.id.parse::<i64>().unwrap_or(0));
61}
62
63/// Build a forest (collection of trees) from a list of tasks.
64///
65/// Uses `parent:*` labels to determine hierarchy. Tasks without a parent label
66/// are roots. Tasks with a parent label that doesn't exist in the list are
67/// also treated as roots (orphaned children become top-level).
68pub fn build_forest(tasks: &[Task]) -> Vec<TreeNode> {
69    fn build_node(
70        id: &str,
71        nodes: &HashMap<String, TreeNode>,
72        children_map: &HashMap<String, Vec<String>>,
73    ) -> Option<TreeNode> {
74        let mut node = nodes.get(id)?.clone();
75
76        if let Some(children_ids) = children_map.get(id) {
77            for child_id in children_ids {
78                if let Some(child_node) = build_node(child_id, nodes, children_map) {
79                    node.children.push(child_node);
80                }
81            }
82        }
83
84        // Sort children by numeric ID for deterministic output
85        sort_by_numeric_id(&mut node.children);
86
87        Some(node)
88    }
89
90    let mut nodes: HashMap<String, TreeNode> = HashMap::new();
91    let mut parent_map: HashMap<String, Option<String>> = HashMap::new();
92
93    // First pass: create nodes and extract parent relationships
94    for task in tasks {
95        let (id, parent_id, node) = match task {
96            Task::External(ext) => {
97                let parent = ext
98                    .labels
99                    .iter()
100                    .find(|l| l.starts_with("parent:"))
101                    .map(|l| {
102                        let parent_num = l.trim_start_matches("parent:");
103                        parent_num.to_string()
104                    });
105                let node = TreeNode::from_external(ext);
106                (ext.id.0.clone(), parent, node)
107            }
108            Task::Internal(int) => {
109                // Internal tasks don't have parent labels (for now)
110                let node = TreeNode::from_internal(int);
111                let id = int
112                    .external_id
113                    .clone()
114                    .unwrap_or_else(|| int.id.to_string());
115                (id, None, node)
116            }
117        };
118
119        parent_map.insert(id.clone(), parent_id);
120        nodes.insert(id, node);
121    }
122
123    // Second pass: build the tree structure
124    let mut root_ids: Vec<String> = Vec::new();
125    let mut children_map: HashMap<String, Vec<String>> = HashMap::new();
126
127    for (id, parent_opt) in &parent_map {
128        match parent_opt {
129            Some(parent_id) => {
130                // If parent exists in our task list, add as child
131                if nodes.contains_key(parent_id) {
132                    children_map
133                        .entry(parent_id.clone())
134                        .or_default()
135                        .push(id.clone());
136                } else {
137                    // Parent not in list, treat as root
138                    root_ids.push(id.clone());
139                }
140            }
141            None => {
142                // No parent, this is a root
143                root_ids.push(id.clone());
144            }
145        }
146    }
147
148    // Third pass: recursively build the tree
149    let mut roots: Vec<TreeNode> = Vec::new();
150    for root_id in root_ids {
151        if let Some(tree) = build_node(&root_id, &nodes, &children_map) {
152            roots.push(tree);
153        }
154    }
155
156    // Sort roots by ID numerically for consistent output
157    sort_by_numeric_id(&mut roots);
158
159    roots
160}
161
162/// Render a tree as ASCII with unicode box-drawing characters.
163pub fn render_tree(root: &TreeNode) -> String {
164    let mut output = String::new();
165    render_node(root, &mut output, "", true, true);
166    output
167}
168
169/// Render a tree node and its children recursively.
170fn render_node(node: &TreeNode, output: &mut String, prefix: &str, is_last: bool, is_root: bool) {
171    let agent = node
172        .agent
173        .as_ref()
174        .map(|a| format!("({a}) "))
175        .unwrap_or_default();
176    let label = format!("#{} [{}] {}{}", node.id, node.status, agent, node.title);
177    if is_root {
178        // Root node format: #30 [blocked] Implement auth system
179        let _ = writeln!(output, "{label}");
180    } else {
181        // Child node format with tree branches
182        let branch = if is_last { "└── " } else { "├── " };
183        let _ = writeln!(output, "{prefix}{branch}{label}");
184    }
185
186    // Render children
187    let child_prefix = if is_root {
188        prefix.to_string()
189    } else if is_last {
190        format!("{prefix}    ")
191    } else {
192        format!("{prefix}│   ")
193    };
194
195    let child_count = node.children.len();
196    for (i, child) in node.children.iter().enumerate() {
197        let child_is_last = i == child_count - 1;
198        render_node(child, output, &child_prefix, child_is_last, false);
199    }
200}
201
202/// Render multiple trees (a forest).
203pub fn render_forest(roots: &[TreeNode]) -> String {
204    if roots.is_empty() {
205        return "No tasks found.".to_string();
206    }
207
208    let mut output = String::new();
209    for (i, root) in roots.iter().enumerate() {
210        output.push_str(&render_tree(root));
211
212        // Add blank line between trees, except for the last one
213        if i < roots.len() - 1 {
214            output.push('\n');
215        }
216    }
217
218    output
219}
220
221/// Render a single tree by ID (for when user requests a specific task tree).
222pub fn render_single_tree(root: &TreeNode, show_no_children_msg: bool) -> String {
223    let mut output = render_tree(root);
224
225    if root.children.is_empty() && show_no_children_msg {
226        output.push_str("    (no children)\n");
227    }
228
229    output
230}
231
232#[cfg(test)]
233mod tests {
234    use super::*;
235    use crate::backends::{ExternalId, ExternalTask};
236
237    fn create_test_task(id: &str, title: &str, _state: &str, labels: &[&str]) -> Task {
238        Task::External(ExternalTask {
239            id: ExternalId(id.to_string()),
240            title: title.to_string(),
241            body: String::new(),
242            state: "open".to_string(),
243            labels: labels.iter().map(ToString::to_string).collect(),
244            author: "test".to_string(),
245            created_at: "2026-01-01T00:00:00Z".to_string(),
246            updated_at: "2026-01-01T00:00:00Z".to_string(),
247            url: format!("https://github.com/test/test/issues/{id}"),
248        })
249    }
250
251    #[test]
252    fn test_build_forest_empty() {
253        let forest = build_forest(&[]);
254        assert!(forest.is_empty());
255    }
256
257    #[test]
258    fn test_build_forest_single_root() {
259        let tasks = vec![create_test_task(
260            "30",
261            "Implement auth",
262            "open",
263            &["status:blocked", "agent:claude"],
264        )];
265
266        let forest = build_forest(&tasks);
267        assert_eq!(forest.len(), 1);
268        assert_eq!(forest[0].id, "30");
269        assert_eq!(forest[0].status, "blocked");
270        assert_eq!(forest[0].agent, Some("claude".to_string()));
271        assert!(forest[0].children.is_empty());
272    }
273
274    #[test]
275    fn test_build_forest_with_children() {
276        let tasks = vec![
277            create_test_task(
278                "30",
279                "Implement auth",
280                "open",
281                &["status:blocked", "agent:claude"],
282            ),
283            create_test_task(
284                "31",
285                "Add user model",
286                "open",
287                &["status:done", "parent:30"],
288            ),
289            create_test_task(
290                "32",
291                "Add login API",
292                "open",
293                &["status:in_progress", "parent:30"],
294            ),
295        ];
296
297        let forest = build_forest(&tasks);
298        assert_eq!(forest.len(), 1);
299        assert_eq!(forest[0].id, "30");
300        assert_eq!(forest[0].children.len(), 2);
301
302        // Children should be sorted by ID
303        assert_eq!(forest[0].children[0].id, "31");
304        assert_eq!(forest[0].children[1].id, "32");
305    }
306
307    #[test]
308    fn test_build_forest_multiple_roots() {
309        let tasks = vec![
310            create_test_task("35", "Refactor DB", "open", &["status:in_progress"]),
311            create_test_task("30", "Implement auth", "open", &["status:blocked"]),
312        ];
313
314        let forest = build_forest(&tasks);
315        assert_eq!(forest.len(), 2);
316        // Should be sorted by ID: 30, 35
317        assert_eq!(forest[0].id, "30");
318        assert_eq!(forest[1].id, "35");
319    }
320
321    #[test]
322    fn test_render_tree() {
323        let root = TreeNode {
324            id: "30".to_string(),
325            title: "Implement auth system".to_string(),
326            status: "blocked".to_string(),
327            agent: Some("claude".to_string()),
328            children: vec![
329                TreeNode {
330                    id: "31".to_string(),
331                    title: "Add user model".to_string(),
332                    status: "done".to_string(),
333                    agent: None,
334                    children: vec![],
335                },
336                TreeNode {
337                    id: "32".to_string(),
338                    title: "Add login API".to_string(),
339                    status: "in_progress".to_string(),
340                    agent: Some("codex".to_string()),
341                    children: vec![],
342                },
343            ],
344        };
345
346        let output = render_tree(&root);
347        assert!(output.contains("#30 [blocked] (claude) Implement auth system"));
348        assert!(output.contains("├── #31 [done] Add user model"));
349        assert!(output.contains("└── #32 [in_progress] (codex) Add login API"));
350    }
351
352    #[test]
353    fn test_render_forest() {
354        let roots = vec![TreeNode {
355            id: "35".to_string(),
356            title: "Refactor database".to_string(),
357            status: "in_progress".to_string(),
358            agent: None,
359            children: vec![],
360        }];
361
362        let output = render_forest(&roots);
363        assert!(output.contains("#35 [in_progress] Refactor database"));
364    }
365
366    #[test]
367    fn test_orphaned_child_becomes_root() {
368        // Task has parent:99 but 99 doesn't exist in our task list
369        let tasks = vec![create_test_task(
370            "31",
371            "Orphan task",
372            "open",
373            &["status:new", "parent:99"],
374        )];
375
376        let forest = build_forest(&tasks);
377        assert_eq!(forest.len(), 1);
378        assert_eq!(forest[0].id, "31");
379        assert!(forest[0].children.is_empty());
380    }
381
382    fn node(id: &str, status: &str, agent: Option<&str>, children: Vec<TreeNode>) -> TreeNode {
383        TreeNode {
384            id: id.to_string(),
385            title: format!("T{id}"),
386            status: status.to_string(),
387            agent: agent.map(ToString::to_string),
388            children,
389        }
390    }
391
392    #[test]
393    fn render_tree_exact_output_for_nested_tree() {
394        let root = node(
395            "1",
396            "blocked",
397            Some("claude"),
398            vec![
399                node(
400                    "2",
401                    "done",
402                    None,
403                    vec![
404                        node("4", "done", Some("codex"), vec![]),
405                        node("5", "new", None, vec![]),
406                    ],
407                ),
408                node("3", "new", None, vec![node("6", "new", None, vec![])]),
409            ],
410        );
411
412        let expected = [
413            "#1 [blocked] (claude) T1",
414            "├── #2 [done] T2",
415            "│   ├── #4 [done] (codex) T4",
416            "│   └── #5 [new] T5",
417            "└── #3 [new] T3",
418            "    └── #6 [new] T6",
419            "",
420        ]
421        .join("\n");
422        assert_eq!(render_tree(&root), expected);
423    }
424
425    #[test]
426    fn render_forest_separates_trees_with_one_blank_line() {
427        let roots = vec![
428            node("1", "new", None, vec![]),
429            node("2", "done", None, vec![]),
430        ];
431        assert_eq!(render_forest(&roots), "#1 [new] T1\n\n#2 [done] T2\n");
432    }
433
434    #[test]
435    fn render_forest_empty_says_no_tasks() {
436        assert_eq!(render_forest(&[]), "No tasks found.");
437    }
438
439    #[test]
440    fn render_single_tree_notes_missing_children_only_when_asked() {
441        let leaf = node("1", "new", None, vec![]);
442        assert_eq!(
443            render_single_tree(&leaf, true),
444            "#1 [new] T1\n    (no children)\n"
445        );
446        assert_eq!(render_single_tree(&leaf, false), "#1 [new] T1\n");
447
448        let parent = node("1", "new", None, vec![node("2", "new", None, vec![])]);
449        assert_eq!(
450            render_single_tree(&parent, true),
451            "#1 [new] T1\n└── #2 [new] T2\n"
452        );
453    }
454
455    #[test]
456    fn build_forest_sorts_numerically_and_non_numeric_ids_sort_first() {
457        let tasks = vec![
458            create_test_task("10", "ten", "open", &["status:new"]),
459            create_test_task("9", "nine", "open", &["status:new"]),
460            create_test_task("abc", "word", "open", &["status:new"]),
461            create_test_task("2", "child b", "open", &["parent:10"]),
462            create_test_task("11", "child a", "open", &["parent:10"]),
463        ];
464
465        let forest = build_forest(&tasks);
466        let root_ids: Vec<&str> = forest.iter().map(|n| n.id.as_str()).collect();
467        assert_eq!(root_ids, ["abc", "9", "10"]);
468        let child_ids: Vec<&str> = forest[2].children.iter().map(|n| n.id.as_str()).collect();
469        assert_eq!(child_ids, ["2", "11"]);
470    }
471
472    #[test]
473    fn from_external_without_labels_has_unknown_status_and_no_agent() {
474        let Task::External(ext) = create_test_task("7", "x", "open", &[]) else {
475            unreachable!()
476        };
477        let node = TreeNode::from_external(&ext);
478        assert_eq!(node.status, "unknown");
479        assert_eq!(node.agent, None);
480    }
481}