Skip to main content

max / goingson

13.5 KB · 364 lines History Blame Raw
1 //! The task blocking graph: edges, per-task graph position, and the whole-graph
2 //! projection the DAG view and `get_task_graph` read.
3 //!
4 //! One relation only. An edge says `blocker` must be Completed before `blocked`
5 //! can be started. See `migrations/sqlite/065_task_dependencies.sql` for why
6 //! there is no second edge kind and why this is not built on
7 //! [`Subtask::linked_task_id`](super::Subtask::linked_task_id).
8 //!
9 //! Nothing here stores blocked-ness as a fact about a task. A task is blocked
10 //! because of the edges around it, and [`GraphPosition`] is the recomputed
11 //! summary of that, never an independently editable flag.
12
13 use crate::id_types::{TaskDependencyId, TaskId};
14 use chrono::{DateTime, Utc};
15 use serde::{Deserialize, Serialize};
16
17 /// Fixed namespace UUID for GoingsOn dependency-edge ids (generated once, never
18 /// changes). See [`TaskDependency::deterministic_id`].
19 const GOINGSON_TASK_DEPENDENCY_NS: uuid::Uuid = uuid::Uuid::from_bytes([
20 0x84, 0x1b, 0x2e, 0xc5, 0x7f, 0x36, 0x5a, 0x90, 0xb4, 0x28, 0x1d, 0x6f, 0x39, 0xa7, 0xc0, 0x1e,
21 ]);
22
23 /// One edge of the blocking graph: `blocker_id` gates `blocked_id`.
24 #[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
25 #[serde(rename_all = "camelCase")]
26 pub struct TaskDependency {
27 /// Deterministic identifier (UUID v5 of `<blocker_id>:<blocked_id>`).
28 pub id: TaskDependencyId,
29 /// The task that has to wait.
30 pub blocked_id: TaskId,
31 /// The task it is waiting on.
32 pub blocker_id: TaskId,
33 /// When the edge was drawn.
34 pub created_at: DateTime<Utc>,
35 }
36
37 impl TaskDependency {
38 /// The deterministic row id for a `(blocker, blocked)` pair.
39 ///
40 /// Content-derived and pure, so two devices that draw the same edge while
41 /// offline produce the same id and the changelog's id-keyed upsert collapses
42 /// them to one row. The pair is ordered in the key (blocker first), so the
43 /// reverse edge is a different id, which it must be: the reverse edge is a
44 /// different, and generally wrong, claim.
45 pub fn deterministic_id(blocker_id: TaskId, blocked_id: TaskId) -> TaskDependencyId {
46 let key = format!("{blocker_id}:{blocked_id}");
47 TaskDependencyId::from(uuid::Uuid::new_v5(
48 &GOINGSON_TASK_DEPENDENCY_NS,
49 key.as_bytes(),
50 ))
51 }
52 }
53
54 /// A task named as the other end of an edge: enough to render a blocker or
55 /// dependent in a list without fetching the whole task.
56 #[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
57 #[serde(rename_all = "camelCase")]
58 pub struct LinkedTaskRef {
59 /// The task at the other end.
60 pub id: TaskId,
61 /// Its short label.
62 pub title: String,
63 /// Its lifecycle status, which is what decides whether it still gates.
64 pub status: super::TaskStatus,
65 /// Its project's name, for cross-project edges (a blocker is frequently in
66 /// another project, and an unqualified title reads as if it were local).
67 pub project_name: Option<String>,
68 }
69
70 impl LinkedTaskRef {
71 /// Whether this task still gates anything downstream.
72 ///
73 /// Only `Completed` satisfies a dependency in the ordinary way. `Deleted`
74 /// also stops gating, because a task that no longer exists cannot be waited
75 /// on and leaving the edge live would strand its dependents forever. That is
76 /// a real event rather than a quiet one, so the repository reports edges
77 /// satisfied this way instead of just dropping them.
78 pub fn is_satisfied(&self) -> bool {
79 matches!(
80 self.status,
81 super::TaskStatus::Completed | super::TaskStatus::Deleted
82 )
83 }
84 }
85
86 /// Where a task sits in the graph. Recomputed from the edges, cached on the
87 /// task row, never edited directly.
88 #[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
89 #[serde(rename_all = "camelCase")]
90 pub struct GraphPosition {
91 /// Sequential steps before this task can start. `0` means ready now.
92 ///
93 /// The LONGEST chain of incomplete blockers ahead of the task, not the
94 /// shortest: a task waits for every one of its blockers, so the chain that
95 /// decides when it opens is the slowest one.
96 pub block_depth: u32,
97 /// How many tasks are transitively downstream, and so are freed by
98 /// finishing this one. The critical-path signal.
99 pub unblocks_count: u32,
100 /// Whether this task sits on a dependency cycle.
101 ///
102 /// The repository refuses to draw a cycle, but two devices can each add a
103 /// legal edge that only forms one once merged. A task in a cycle can never
104 /// become ready, so it reads as blocked and is reported here for repair
105 /// rather than being silently dropped from every view.
106 pub in_cycle: bool,
107 }
108
109 impl GraphPosition {
110 /// Whether anything incomplete is currently in this task's way.
111 pub fn is_blocked(&self) -> bool {
112 self.block_depth > 0
113 }
114
115 /// Whether this task can be started right now.
116 pub fn is_ready(&self) -> bool {
117 self.block_depth == 0
118 }
119 }
120
121 /// The whole blocking graph for a scope (a project, or a user's tasks), as the
122 /// DAG view and `get_task_graph` want it: nodes with their positions, the edges
123 /// between them, and whatever cycles are present.
124 #[derive(Debug, Clone, Default, Serialize, Deserialize)]
125 #[serde(rename_all = "camelCase")]
126 pub struct TaskGraph {
127 /// Every task in scope that touches at least one edge, plus its position.
128 pub nodes: Vec<TaskGraphNode>,
129 /// The edges among those nodes.
130 pub edges: Vec<TaskDependency>,
131 /// Each cycle found, as the task ids on it. Empty in the healthy case.
132 pub cycles: Vec<Vec<TaskId>>,
133 }
134
135 impl TaskGraph {
136 /// The tasks that can be started right now, most-unblocking first.
137 ///
138 /// This is the ordering the ready-work views want: among tasks that are
139 /// equally startable, the one that frees the most downstream work is the one
140 /// worth starting.
141 pub fn ready(&self) -> Vec<&TaskGraphNode> {
142 let mut ready: Vec<&TaskGraphNode> = self
143 .nodes
144 .iter()
145 .filter(|n| n.position.is_ready())
146 .collect();
147 ready.sort_by_key(|n| std::cmp::Reverse(n.position.unblocks_count));
148 ready
149 }
150
151 /// Whether the graph is a DAG. False means sync merged a cycle into it.
152 pub fn is_acyclic(&self) -> bool {
153 self.cycles.is_empty()
154 }
155 }
156
157 /// One task in a [`TaskGraph`].
158 #[derive(Debug, Clone, Serialize, Deserialize)]
159 #[serde(rename_all = "camelCase")]
160 pub struct TaskGraphNode {
161 /// The task.
162 pub id: TaskId,
163 /// Its short label.
164 pub title: String,
165 /// Its lifecycle status.
166 pub status: super::TaskStatus,
167 /// Its priority.
168 pub priority: super::Priority,
169 /// Its project, if filed.
170 pub project_id: Option<crate::id_types::ProjectId>,
171 /// Its graph position.
172 pub position: GraphPosition,
173 }
174
175 /// What a task still waits on, judged against a day plan.
176 ///
177 /// The blocking rule everywhere else is absolute: a task is unavailable until
178 /// its blockers are done. Inside a plan that is too strict, because the plan is
179 /// itself a statement about order. Scheduling A says A happens today, which is
180 /// exactly the thing that makes it reasonable to also schedule B.
181 ///
182 /// So a plan widens the "has this stopped gating" test from `Completed` to
183 /// "completed, or already in this plan". The widening is not stored and is not a
184 /// property of the task; it holds only for the plan it was computed against.
185 ///
186 /// This cascades without special-casing. With A blocking B blocking C,
187 /// scheduling A unlocks B, and scheduling B unlocks C, because each pass reads
188 /// the plan as it now stands.
189 #[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
190 #[serde(rename_all = "camelCase")]
191 pub struct PlanGate {
192 /// The blockers that are still unfinished, in the order the edges were
193 /// drawn. Never empty: a task with nothing in its way has no gate at all.
194 pub after: Vec<LinkedTaskRef>,
195 /// Whether every unfinished blocker is itself in the plan, which is what
196 /// makes this task schedulable despite being blocked.
197 pub unlocked_by_plan: bool,
198 /// Whether a blocker in the plan is scheduled to start later than this task
199 /// does.
200 ///
201 /// Presence-only gating permits this on purpose: enforcing the order would
202 /// mean a task leaving the plan as it is dragged, which fights the person
203 /// rearranging their day. The incoherence is reported instead, and the
204 /// marker naming the blocker is the nudge.
205 pub out_of_order: bool,
206 }
207
208 impl PlanGate {
209 /// The blocker to name in a one-line marker: the first still-unfinished one.
210 ///
211 /// One name rather than a list because this renders inside a task chip. The
212 /// count carries the rest.
213 pub fn lead_blocker(&self) -> Option<&LinkedTaskRef> {
214 self.after.first()
215 }
216 }
217
218 /// Why an edge could not be drawn.
219 ///
220 /// Both variants are refusals rather than failures: the caller asked for
221 /// something the graph cannot hold, and the useful reply names the path that
222 /// makes it impossible.
223 #[derive(Debug, Clone, PartialEq, Eq)]
224 pub enum DependencyRejection {
225 /// The edge would close a cycle. Carries the existing path from the
226 /// prospective blocked task back to the prospective blocker, so the caller
227 /// can show which chain is already in the way instead of just refusing.
228 WouldCycle { path: Vec<TaskId> },
229 /// A task cannot block itself.
230 SelfEdge { task_id: TaskId },
231 }
232
233 impl std::fmt::Display for DependencyRejection {
234 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
235 match self {
236 Self::WouldCycle { path } => {
237 let chain: Vec<String> = path.iter().map(ToString::to_string).collect();
238 write!(
239 f,
240 "that edge would close a dependency cycle: {} already depends on it",
241 chain.join(" -> ")
242 )
243 }
244 Self::SelfEdge { task_id } => write!(f, "task {task_id} cannot block itself"),
245 }
246 }
247 }
248
249 impl std::error::Error for DependencyRejection {}
250
251 #[cfg(test)]
252 mod tests {
253 use super::*;
254 use crate::models::{Priority, TaskStatus};
255
256 fn node(title: &str, depth: u32, unblocks: u32) -> TaskGraphNode {
257 TaskGraphNode {
258 id: TaskId::new(),
259 title: title.to_string(),
260 status: TaskStatus::Pending,
261 priority: Priority::Medium,
262 project_id: None,
263 position: GraphPosition {
264 block_depth: depth,
265 unblocks_count: unblocks,
266 in_cycle: false,
267 },
268 }
269 }
270
271 #[test]
272 fn edge_id_is_stable_content_derived_and_directional() {
273 let a = TaskId::new();
274 let b = TaskId::new();
275 assert_eq!(
276 TaskDependency::deterministic_id(a, b),
277 TaskDependency::deterministic_id(a, b),
278 "same pair must yield the same id so two devices converge"
279 );
280 assert_ne!(
281 TaskDependency::deterministic_id(a, b),
282 TaskDependency::deterministic_id(b, a),
283 "the reverse edge is a different claim and must be a different row"
284 );
285 assert_eq!(
286 TaskDependency::deterministic_id(a, b)
287 .as_uuid()
288 .get_version_num(),
289 5
290 );
291 }
292
293 #[test]
294 fn a_position_is_blocked_exactly_when_it_has_depth() {
295 let ready = GraphPosition::default();
296 assert!(ready.is_ready());
297 assert!(!ready.is_blocked());
298
299 let waiting = GraphPosition {
300 block_depth: 1,
301 ..Default::default()
302 };
303 assert!(waiting.is_blocked());
304 assert!(!waiting.is_ready());
305 }
306
307 #[test]
308 fn completed_and_deleted_blockers_stop_gating_but_nothing_else_does() {
309 let mut r = LinkedTaskRef {
310 id: TaskId::new(),
311 title: "blocker".into(),
312 status: TaskStatus::Pending,
313 project_name: None,
314 };
315 assert!(!r.is_satisfied());
316 r.status = TaskStatus::Started;
317 assert!(!r.is_satisfied(), "started is not finished");
318 r.status = TaskStatus::Completed;
319 assert!(r.is_satisfied());
320 r.status = TaskStatus::Deleted;
321 assert!(
322 r.is_satisfied(),
323 "a deleted blocker would otherwise strand its dependents forever"
324 );
325 }
326
327 #[test]
328 fn ready_returns_only_startable_nodes_most_unblocking_first() {
329 let graph = TaskGraph {
330 nodes: vec![
331 node("frees one", 0, 1),
332 node("waiting", 2, 9),
333 node("frees four", 0, 4),
334 node("frees none", 0, 0),
335 ],
336 edges: vec![],
337 cycles: vec![],
338 };
339 let ready: Vec<&str> = graph.ready().iter().map(|n| n.title.as_str()).collect();
340 assert_eq!(
341 ready,
342 vec!["frees four", "frees one", "frees none"],
343 "blocked nodes are excluded however much they would free"
344 );
345 }
346
347 #[test]
348 fn a_graph_with_a_cycle_is_not_acyclic() {
349 let mut graph = TaskGraph::default();
350 assert!(graph.is_acyclic(), "an empty graph is trivially a DAG");
351 graph.cycles.push(vec![TaskId::new(), TaskId::new()]);
352 assert!(!graph.is_acyclic());
353 }
354
355 #[test]
356 fn a_cycle_rejection_names_the_path_already_in_the_way() {
357 let a = TaskId::new();
358 let b = TaskId::new();
359 let msg = DependencyRejection::WouldCycle { path: vec![a, b] }.to_string();
360 assert!(msg.contains(&a.to_string()) && msg.contains(&b.to_string()));
361 assert!(msg.contains("->"), "the path reads as a chain");
362 }
363 }
364