1//! Diagnose and repair CRDT document integrity.
2//!
3//! Detects dangling references, dependency cycles, and parent-chain
4//! cycles that can arise from concurrent CRDT edits across peers.
5//! With `--fix`, applies deterministic, non-destructive repairs.
6
7use std::collections::{HashMap, HashSet};
8use std::path::Path;
9
10use anyhow::{anyhow, Result};
11use serde::Serialize;
12
13use crate::db;
14use crate::model::{now_utc, Status, Task, TaskId};
15
16/// Categories of integrity issues that doctor can detect.
17#[derive(Debug, Clone, Serialize)]
18#[serde(rename_all = "snake_case")]
19enum FindingKind {
20 DanglingParent,
21 DanglingBlocker,
22 BlockerCycle,
23 ParentCycle,
24}
25
26/// A single integrity issue found during diagnosis.
27#[derive(Debug, Clone, Serialize)]
28struct Finding {
29 kind: FindingKind,
30 /// Short display ID (`td-XXXXXXX`) of the primarily affected task.
31 task: String,
32 /// Human-readable description of the issue.
33 detail: String,
34 /// Whether this finding affects runtime behavior. Blocker cycles
35 /// involving closed or tombstoned tasks are inert because
36 /// `partition_blockers` already treats them as resolved.
37 active: bool,
38 /// Whether `--fix` repaired this finding.
39 fixed: bool,
40}
41
42/// Aggregate counts for the doctor report.
43#[derive(Debug, Clone, Default, Serialize)]
44struct Summary {
45 dangling_parents: usize,
46 dangling_blockers: usize,
47 blocker_cycles: usize,
48 parent_cycles: usize,
49 total: usize,
50 fixed: usize,
51}
52
53/// Full doctor report, serialised as JSON when `--json` is passed.
54#[derive(Debug, Clone, Serialize)]
55struct Report {
56 findings: Vec<Finding>,
57 summary: Summary,
58}
59
60/// Repair action to apply when `--fix` is requested.
61enum Repair {
62 ClearParent(TaskId),
63 RemoveBlocker(TaskId, TaskId),
64}
65
66pub fn run(root: &Path, fix: bool, json: bool) -> Result<()> {
67 let store = db::open(root)?;
68 let tasks = store.list_tasks_unfiltered()?;
69
70 // Build lookup structures.
71 let all_ids: HashSet<String> = tasks.iter().map(|t| t.id.as_str().to_string()).collect();
72 let open_ids: HashSet<String> = tasks
73 .iter()
74 .filter(|t| t.status != Status::Closed && t.deleted_at.is_none())
75 .map(|t| t.id.as_str().to_string())
76 .collect();
77
78 let mut findings: Vec<Finding> = Vec::new();
79 let mut repairs: Vec<Repair> = Vec::new();
80
81 check_dangling_parents(&tasks, &all_ids, &mut findings, &mut repairs);
82 check_dangling_blockers(&tasks, &all_ids, &mut findings, &mut repairs);
83 check_blocker_cycles(&tasks, &all_ids, &open_ids, &mut findings, &mut repairs)?;
84 check_parent_cycles(&tasks, &all_ids, &mut findings, &mut repairs)?;
85
86 if fix && !repairs.is_empty() {
87 store.apply_and_persist(|doc| {
88 let tasks_map = doc.get_map("tasks");
89 let ts = now_utc();
90
91 for repair in &repairs {
92 match repair {
93 Repair::ClearParent(task_id) => {
94 let task = db::get_task_map(&tasks_map, task_id)?
95 .ok_or_else(|| anyhow!("task {} not found during repair", task_id))?;
96 task.insert("parent", "")?;
97 task.insert("updated_at", ts.clone())?;
98 }
99 Repair::RemoveBlocker(task_id, blocker_id) => {
100 let task = db::get_task_map(&tasks_map, task_id)?
101 .ok_or_else(|| anyhow!("task {} not found during repair", task_id))?;
102 let blockers = db::get_or_create_child_map(&task, "blockers")?;
103 blockers.delete(blocker_id.as_str())?;
104 task.insert("updated_at", ts.clone())?;
105 }
106 }
107 }
108 Ok(())
109 })?;
110
111 for finding in &mut findings {
112 if finding.active {
113 finding.fixed = true;
114 }
115 }
116 }
117
118 let summary = build_summary(&findings);
119 let report = Report { findings, summary };
120
121 if json {
122 println!("{}", serde_json::to_string(&report)?);
123 } else {
124 print_human(&report, fix);
125 }
126
127 Ok(())
128}
129
130/// Detect parent fields that reference missing or tombstoned tasks.
131///
132/// Skips tombstoned tasks — their stale references are not actionable.
133fn check_dangling_parents(
134 tasks: &[Task],
135 all_ids: &HashSet<String>,
136 findings: &mut Vec<Finding>,
137 repairs: &mut Vec<Repair>,
138) {
139 let task_map: std::collections::HashMap<&str, &Task> =
140 tasks.iter().map(|t| (t.id.as_str(), t)).collect();
141
142 for task in tasks {
143 // Tombstoned tasks are already deleted; stale refs on them aren't actionable.
144 if task.deleted_at.is_some() {
145 continue;
146 }
147
148 let Some(parent) = &task.parent else {
149 continue;
150 };
151
152 if !all_ids.contains(parent.as_str()) {
153 findings.push(Finding {
154 kind: FindingKind::DanglingParent,
155 task: task.id.to_string(),
156 detail: format!(
157 "parent references missing task {}",
158 TaskId::display_id(parent.as_str()),
159 ),
160 active: true,
161 fixed: false,
162 });
163 repairs.push(Repair::ClearParent(task.id.clone()));
164 continue;
165 }
166
167 // Parent exists but is tombstoned — the subtask is orphaned.
168 if let Some(pt) = task_map.get(parent.as_str()) {
169 if pt.deleted_at.is_some() {
170 findings.push(Finding {
171 kind: FindingKind::DanglingParent,
172 task: task.id.to_string(),
173 detail: format!(
174 "parent references tombstoned task {}",
175 TaskId::display_id(parent.as_str()),
176 ),
177 active: true,
178 fixed: false,
179 });
180 repairs.push(Repair::ClearParent(task.id.clone()));
181 }
182 }
183 }
184}
185
186/// Detect blocker entries that reference tasks not present in the document.
187///
188/// Skips tombstoned tasks — their stale references are not actionable.
189fn check_dangling_blockers(
190 tasks: &[Task],
191 all_ids: &HashSet<String>,
192 findings: &mut Vec<Finding>,
193 repairs: &mut Vec<Repair>,
194) {
195 for task in tasks {
196 if task.deleted_at.is_some() {
197 continue;
198 }
199
200 for blocker in &task.blockers {
201 if !all_ids.contains(blocker.as_str()) {
202 findings.push(Finding {
203 kind: FindingKind::DanglingBlocker,
204 task: task.id.to_string(),
205 detail: format!(
206 "blocker references missing task {}",
207 TaskId::display_id(blocker.as_str()),
208 ),
209 active: true,
210 fixed: false,
211 });
212 repairs.push(Repair::RemoveBlocker(task.id.clone(), blocker.clone()));
213 }
214 }
215 }
216}
217
218/// Detect cycles in the blocker graph.
219///
220/// Iteratively finds one cycle at a time, records the deterministic
221/// edge to break (lowest blocker ULID in the cycle), removes that edge
222/// from the working graph, and repeats until acyclic.
223///
224/// Cycles where every node is open are "active" — they trap tasks out
225/// of `ready`/`next`. Cycles containing any closed or tombstoned node
226/// are "inert" — `partition_blockers` already resolves them at runtime.
227/// Only active cycles are repaired by `--fix`.
228fn check_blocker_cycles(
229 tasks: &[Task],
230 all_ids: &HashSet<String>,
231 open_ids: &HashSet<String>,
232 findings: &mut Vec<Finding>,
233 repairs: &mut Vec<Repair>,
234) -> Result<()> {
235 // Build adjacency: task → set of blockers (only edges where both
236 // endpoints exist, to avoid mixing up dangling-ref findings).
237 let mut graph: HashMap<String, HashSet<String>> = HashMap::new();
238 for task in tasks {
239 for blocker in &task.blockers {
240 if all_ids.contains(blocker.as_str()) {
241 graph
242 .entry(task.id.as_str().to_string())
243 .or_default()
244 .insert(blocker.as_str().to_string());
245 }
246 }
247 }
248
249 loop {
250 let Some(cycle) = find_cycle_dfs(&graph) else {
251 break;
252 };
253
254 // Determine which edge to break: the one whose blocker ULID
255 // is lexicographically lowest. Edges in the cycle are
256 // (cycle[0] → cycle[1]), (cycle[1] → cycle[2]), etc.
257 let mut best: Option<(String, String)> = None;
258 for pair in cycle.windows(2) {
259 let blocker = &pair[1];
260 if best.as_ref().is_none_or(|(_, b)| blocker < b) {
261 best = Some((pair[0].clone(), blocker.clone()));
262 }
263 }
264 let (task_id, blocker_id) = best.expect("cycle must have at least one edge");
265
266 let active = cycle[..cycle.len() - 1]
267 .iter()
268 .all(|id| open_ids.contains(id));
269
270 // Build a human-readable cycle string using short IDs.
271 let display: Vec<String> = cycle.iter().map(|id| TaskId::display_id(id)).collect();
272 let cycle_str = display.join(" → ");
273
274 findings.push(Finding {
275 kind: FindingKind::BlockerCycle,
276 task: TaskId::display_id(&task_id),
277 detail: cycle_str,
278 active,
279 fixed: false,
280 });
281
282 if active {
283 repairs.push(Repair::RemoveBlocker(
284 TaskId::parse(&task_id)?,
285 TaskId::parse(&blocker_id)?,
286 ));
287 }
288
289 // Remove the edge from the working graph so the next iteration
290 // can find further cycles (or terminate).
291 if let Some(set) = graph.get_mut(&task_id) {
292 set.remove(&blocker_id);
293 }
294 }
295
296 Ok(())
297}
298
299/// Detect cycles in the parent-child hierarchy.
300///
301/// Follows each task's parent chain; if we revisit a task already in the
302/// current path, we have a cycle. Repairs clear the parent field on the
303/// task with the lexicographically lowest ULID in the cycle.
304fn check_parent_cycles(
305 tasks: &[Task],
306 all_ids: &HashSet<String>,
307 findings: &mut Vec<Finding>,
308 repairs: &mut Vec<Repair>,
309) -> Result<()> {
310 let parent_map: HashMap<String, String> = tasks
311 .iter()
312 .filter_map(|t| {
313 t.parent.as_ref().and_then(|p| {
314 if all_ids.contains(p.as_str()) {
315 Some((t.id.as_str().to_string(), p.as_str().to_string()))
316 } else {
317 None // dangling parents handled separately
318 }
319 })
320 })
321 .collect();
322
323 let mut globally_visited: HashSet<String> = HashSet::new();
324
325 for task in tasks {
326 let start = task.id.as_str().to_string();
327 if globally_visited.contains(&start) {
328 continue;
329 }
330
331 let mut path: Vec<String> = Vec::new();
332 let mut path_set: HashSet<String> = HashSet::new();
333 let mut current = Some(start.clone());
334
335 while let Some(node) = current {
336 if path_set.contains(&node) {
337 // Found a cycle. Extract just the cycle portion.
338 let pos = path.iter().position(|n| *n == node).unwrap();
339 let mut cycle: Vec<String> = path[pos..].to_vec();
340 cycle.push(node); // close the loop
341
342 let display: Vec<String> = cycle.iter().map(|id| TaskId::display_id(id)).collect();
343 let cycle_str = display.join(" → ");
344
345 // The task with the lowest ULID gets its parent cleared.
346 let lowest = cycle[..cycle.len() - 1]
347 .iter()
348 .min()
349 .expect("cycle must have at least one node")
350 .clone();
351
352 findings.push(Finding {
353 kind: FindingKind::ParentCycle,
354 task: TaskId::display_id(&lowest),
355 detail: cycle_str,
356 active: true,
357 fixed: false,
358 });
359 repairs.push(Repair::ClearParent(TaskId::parse(&lowest)?));
360 break;
361 }
362 if globally_visited.contains(&node) {
363 break;
364 }
365 path_set.insert(node.clone());
366 path.push(node.clone());
367 current = parent_map.get(&node).cloned();
368 }
369
370 for node in &path {
371 globally_visited.insert(node.clone());
372 }
373 }
374
375 Ok(())
376}
377
378/// Find a single cycle in a directed graph using DFS.
379///
380/// Returns the cycle as a vec of node IDs where the first and last
381/// elements are the same (e.g. `[A, B, C, A]`), or `None` if acyclic.
382fn find_cycle_dfs(graph: &HashMap<String, HashSet<String>>) -> Option<Vec<String>> {
383 let mut visited: HashSet<String> = HashSet::new();
384
385 // Sort keys for deterministic traversal order.
386 let mut nodes: Vec<&String> = graph.keys().collect();
387 nodes.sort();
388
389 for start in nodes {
390 if visited.contains(start) {
391 continue;
392 }
393 let mut path: Vec<String> = Vec::new();
394 let mut path_set: HashSet<String> = HashSet::new();
395 if let Some(cycle) = dfs_visit(start, graph, &mut visited, &mut path, &mut path_set) {
396 return Some(cycle);
397 }
398 }
399 None
400}
401
402/// Recursive DFS helper for cycle detection.
403fn dfs_visit(
404 node: &str,
405 graph: &HashMap<String, HashSet<String>>,
406 visited: &mut HashSet<String>,
407 path: &mut Vec<String>,
408 path_set: &mut HashSet<String>,
409) -> Option<Vec<String>> {
410 visited.insert(node.to_string());
411 path_set.insert(node.to_string());
412 path.push(node.to_string());
413
414 if let Some(neighbors) = graph.get(node) {
415 // Sort neighbors for deterministic cycle detection.
416 let mut sorted: Vec<&String> = neighbors.iter().collect();
417 sorted.sort();
418
419 for neighbor in sorted {
420 if path_set.contains(neighbor.as_str()) {
421 let pos = path.iter().position(|n| n == neighbor).unwrap();
422 let mut cycle = path[pos..].to_vec();
423 cycle.push(neighbor.clone());
424 return Some(cycle);
425 }
426 if !visited.contains(neighbor.as_str()) {
427 if let Some(cycle) = dfs_visit(neighbor, graph, visited, path, path_set) {
428 return Some(cycle);
429 }
430 }
431 }
432 }
433
434 path_set.remove(node);
435 path.pop();
436 None
437}
438
439fn build_summary(findings: &[Finding]) -> Summary {
440 let mut s = Summary::default();
441 for f in findings {
442 match f.kind {
443 FindingKind::DanglingParent => s.dangling_parents += 1,
444 FindingKind::DanglingBlocker => s.dangling_blockers += 1,
445 FindingKind::BlockerCycle => s.blocker_cycles += 1,
446 FindingKind::ParentCycle => s.parent_cycles += 1,
447 }
448 s.total += 1;
449 if f.fixed {
450 s.fixed += 1;
451 }
452 }
453 s
454}
455
456fn print_human(report: &Report, fix: bool) {
457 let c = crate::color::stderr_theme();
458
459 if report.findings.is_empty() {
460 eprintln!("{}info:{} no issues found", c.green, c.reset);
461 return;
462 }
463
464 for f in &report.findings {
465 let short = &f.task;
466 let kind_label = match f.kind {
467 FindingKind::DanglingParent => "dangling parent",
468 FindingKind::DanglingBlocker => "dangling blocker",
469 FindingKind::BlockerCycle => {
470 if f.active {
471 "blocker cycle (active)"
472 } else {
473 "blocker cycle (inert)"
474 }
475 }
476 FindingKind::ParentCycle => "parent cycle",
477 };
478
479 if f.fixed {
480 eprintln!(
481 "{}fixed:{} {}: {} — {}",
482 c.green, c.reset, kind_label, short, f.detail
483 );
484 } else {
485 eprintln!(
486 "{}issue:{} {}: {} — {}",
487 c.yellow, c.reset, kind_label, short, f.detail
488 );
489 }
490 }
491
492 eprintln!();
493 let n = report.summary.total;
494 let issue_word = if n == 1 { "issue" } else { "issues" };
495 if fix {
496 eprintln!(
497 "{} {issue_word} found, {} fixed",
498 report.summary.total, report.summary.fixed,
499 );
500 } else {
501 eprintln!("{n} {issue_word} found. Run with --fix to repair.");
502 }
503}