ralph/queue/graph/
types.rs

1//! Core types for the queue dependency graph.
2//!
3//! Responsibilities:
4//! - Define the graph data model (`TaskNode`, `DependencyGraph`) and public result types.
5//! - Provide minimal "core" `DependencyGraph` methods that do not belong to algorithms/traversal.
6//!
7//! Not handled here:
8//! - Building graphs from queue files (see `build`).
9//! - Graph algorithms (see `algorithms`).
10//! - Chain traversal utilities (see `traversal`).
11//!
12//! Invariants/assumptions:
13//! - `DependencyGraph` keys are canonicalized task IDs (trimmed).
14//! - Missing task IDs queried via `is_task_completed` are treated as completed (non-blockers).
15
16use crate::contracts::{Task, TaskStatus};
17use std::collections::HashMap;
18
19/// A node in the dependency graph representing a task and its relationships.
20#[derive(Debug, Clone)]
21pub struct TaskNode {
22    /// The task data.
23    pub task: Task,
24    /// IDs of tasks this task depends on (upstream dependencies).
25    pub dependencies: Vec<String>,
26    /// IDs of tasks that depend on this task (downstream dependents).
27    pub dependents: Vec<String>,
28    /// IDs of tasks this task blocks (must complete before blocked tasks can run).
29    pub blocks: Vec<String>,
30    /// IDs of tasks that block this task (reverse of blocks).
31    pub blocked_by: Vec<String>,
32    /// IDs of tasks this task relates to (loose coupling).
33    pub relates_to: Vec<String>,
34    /// IDs of tasks that relate to this task (reverse of relates_to).
35    pub related_by: Vec<String>,
36    /// Task ID that this task duplicates (if any).
37    pub duplicates: Option<String>,
38    /// IDs of tasks that duplicate this task.
39    pub duplicated_by: Vec<String>,
40}
41
42/// Dependency graph containing all tasks and their relationships.
43#[derive(Debug, Clone)]
44pub struct DependencyGraph {
45    pub(crate) nodes: HashMap<String, TaskNode>,
46    pub(crate) roots: Vec<String>,
47    pub(crate) leaves: Vec<String>,
48}
49
50/// Result of critical path analysis.
51#[derive(Debug, Clone)]
52pub struct CriticalPathResult {
53    /// Task IDs in the critical path (from root to leaf, following `dependencies`).
54    pub path: Vec<String>,
55    /// Number of tasks in the path.
56    pub length: usize,
57    /// Whether any task in the path is blocking (not done/rejected).
58    pub is_blocked: bool,
59}
60
61/// Output format for graph serialization.
62#[derive(Debug, Clone, Copy, PartialEq, Eq)]
63pub enum GraphFormat {
64    /// ASCII art tree structure.
65    Tree,
66    /// Graphviz DOT format.
67    Dot,
68    /// JSON format.
69    Json,
70    /// Flat list with indentation.
71    List,
72}
73
74/// Result of a bounded chain traversal.
75#[derive(Debug, Clone)]
76pub struct BoundedChainResult {
77    /// Task IDs collected during traversal (at most `limit` items).
78    pub task_ids: Vec<String>,
79    /// True if there were more tasks available beyond the limit.
80    pub truncated: bool,
81}
82
83impl BoundedChainResult {
84    /// Create a bounded result from a full chain, truncating to `limit`.
85    pub fn from_full_chain(chain: Vec<String>, limit: usize) -> Self {
86        if limit == 0 {
87            return Self {
88                task_ids: Vec::new(),
89                truncated: !chain.is_empty(),
90            };
91        }
92
93        if chain.len() <= limit {
94            Self {
95                task_ids: chain,
96                truncated: false,
97            }
98        } else {
99            Self {
100                task_ids: chain.into_iter().take(limit).collect(),
101                truncated: true,
102            }
103        }
104    }
105}
106
107impl DependencyGraph {
108    pub(crate) fn from_parts(
109        nodes: HashMap<String, TaskNode>,
110        roots: Vec<String>,
111        leaves: Vec<String>,
112    ) -> Self {
113        Self {
114            nodes,
115            roots,
116            leaves,
117        }
118    }
119
120    /// Get a node by task ID.
121    pub fn get(&self, task_id: &str) -> Option<&TaskNode> {
122        self.nodes.get(task_id)
123    }
124
125    /// Check if the graph contains a task.
126    pub fn contains(&self, task_id: &str) -> bool {
127        self.nodes.contains_key(task_id)
128    }
129
130    /// Get all task IDs in the graph.
131    pub fn task_ids(&self) -> impl Iterator<Item = &String> {
132        self.nodes.keys()
133    }
134
135    /// Get root node IDs (tasks with no dependents).
136    pub fn roots(&self) -> &[String] {
137        &self.roots
138    }
139
140    /// Get leaf node IDs (tasks with no dependencies).
141    pub fn leaves(&self) -> &[String] {
142        &self.leaves
143    }
144
145    /// Get the number of tasks in the graph.
146    pub fn len(&self) -> usize {
147        self.nodes.len()
148    }
149
150    /// Check if the graph is empty.
151    pub fn is_empty(&self) -> bool {
152        self.nodes.is_empty()
153    }
154
155    /// Returns true if the task is on any critical path.
156    pub fn is_on_critical_path(
157        &self,
158        task_id: &str,
159        critical_paths: &[CriticalPathResult],
160    ) -> bool {
161        critical_paths
162            .iter()
163            .any(|cp| cp.path.iter().any(|id| id == task_id))
164    }
165
166    /// Check if a task is completed (done or rejected). Missing tasks are treated as completed.
167    pub fn is_task_completed(&self, task_id: &str) -> bool {
168        self.get(task_id)
169            .map(|n| matches!(n.task.status, TaskStatus::Done | TaskStatus::Rejected))
170            .unwrap_or(true)
171    }
172
173    pub(crate) fn values(&self) -> impl Iterator<Item = &TaskNode> {
174        self.nodes.values()
175    }
176}
ralph/queue/graph/types.rs

ralph/queue/graph/
types.rs
