1use std::collections::{BTreeSet, HashMap};
27
28use crate::snapshot::{
29 Dependency, DependencyKind, DependencyMode, Diagnostic, ParsedTasks, Schedule, ScheduleTotals,
30 ScheduledTask, Severity, Task, TaskState,
31};
32
33#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35pub enum PhaseKind {
36 Setup,
38 Foundational,
40 Story,
42 Polish,
44 Convergence,
46 Other,
48}
49
50#[must_use]
52pub fn classify(title: &str, has_story_labels: bool) -> PhaseKind {
53 let t = title.to_lowercase();
54 if t.contains("convergence") {
55 PhaseKind::Convergence
56 } else if t.contains("polish") {
57 PhaseKind::Polish
58 } else if has_story_labels || names_a_user_story(&t) {
59 PhaseKind::Story
60 } else if t.contains("foundational") {
61 PhaseKind::Foundational
62 } else if t.contains("setup") {
63 PhaseKind::Setup
64 } else {
65 PhaseKind::Other
66 }
67}
68
69fn names_a_user_story(lower: &str) -> bool {
70 lower.match_indices("user story").any(|(i, m)| {
71 lower[i + m.len()..]
72 .trim_start()
73 .starts_with(|c: char| c.is_ascii_digit())
74 })
75}
76
77struct Group {
79 kind: PhaseKind,
80 blocks: Vec<Vec<usize>>,
82}
83
84type OpenGroup<'t> = (Option<&'t str>, Vec<Vec<usize>>, Option<&'t str>);
86
87fn groups(tasks: &[Task]) -> Vec<Group> {
88 let mut out: Vec<OpenGroup<'_>> = Vec::new();
89 for (i, t) in tasks.iter().enumerate() {
90 let phase = t.phase.as_deref();
91 let sub = t.subsection.as_deref();
92 match out.last_mut() {
93 Some((p, blocks, last_sub)) if *p == phase => {
94 if *last_sub == sub {
95 if let Some(b) = blocks.last_mut() {
96 b.push(i);
97 }
98 } else {
99 blocks.push(vec![i]);
100 *last_sub = sub;
101 }
102 }
103 _ => out.push((phase, vec![vec![i]], sub)),
104 }
105 }
106 out.into_iter()
107 .map(|(phase, blocks, _)| {
108 let labelled = blocks.iter().flatten().any(|&i| tasks[i].story.is_some());
109 Group {
110 kind: classify(phase.unwrap_or(""), labelled),
111 blocks,
112 }
113 })
114 .collect()
115}
116
117#[must_use]
119pub fn schedule(parsed: &ParsedTasks) -> (Schedule, Vec<Diagnostic>) {
120 let tasks = &parsed.tasks;
121 let mut diags = Vec::new();
122 let index: HashMap<&str, usize> = tasks
123 .iter()
124 .enumerate()
125 .rev() .map(|(i, t)| (t.id.as_str(), i))
127 .collect();
128
129 let mut structural: Vec<Vec<usize>> = vec![Vec::new(); tasks.len()];
131 let declared = parsed.dependency_mode == DependencyMode::Declared;
132 let chain = parsed.dependency_mode == DependencyMode::Chain;
133 let groups = groups(tasks);
134 for (g, group) in groups.iter().enumerate() {
135 if chain {
136 let earlier: Vec<usize> = groups[..g]
137 .iter()
138 .flat_map(|e| e.blocks.iter().flatten().copied())
139 .collect();
140 let mut previous: Option<usize> = None;
141 for &i in group.blocks.iter().flatten() {
142 let mut deps = earlier.clone();
143 deps.extend(previous);
144 structural[i] = deps;
145 previous = Some(i);
146 }
147 continue;
148 }
149 let phase_barrier: Vec<usize> = groups[..g]
150 .iter()
151 .filter(|earlier| group.kind != PhaseKind::Story || earlier.kind != PhaseKind::Story)
152 .flat_map(|earlier| earlier.blocks.iter().flatten().copied())
153 .collect();
154 for (b, block) in group.blocks.iter().enumerate() {
155 let sub_barrier: Vec<usize> = group.blocks[..b].iter().flatten().copied().collect();
156 let mut last_serial: Option<usize> = None;
157 let mut run: Vec<usize> = Vec::new();
158 for &i in block {
159 let mut deps = phase_barrier.clone();
160 if declared {
161 structural[i] = deps;
162 continue;
163 }
164 deps.extend(&sub_barrier);
165 if tasks[i].parallel {
166 deps.extend(last_serial);
167 run.push(i);
168 } else {
169 if run.is_empty() {
170 deps.extend(last_serial);
171 } else {
172 deps.append(&mut run);
173 }
174 last_serial = Some(i);
175 }
176 structural[i] = deps;
177 }
178 }
179 }
180
181 let mut direct: Vec<Vec<Dependency>> = Vec::with_capacity(tasks.len());
183 let mut edges: Vec<Vec<usize>> = Vec::with_capacity(tasks.len());
184 for (i, t) in tasks.iter().enumerate() {
185 let mut seen = BTreeSet::new();
186 let mut deps = Vec::new();
187 let mut resolved = Vec::new();
188 for &d in &structural[i] {
189 if seen.insert(tasks[d].id.as_str()) {
190 deps.push(Dependency {
191 id: tasks[d].id.clone(),
192 kind: DependencyKind::Structural,
193 missing: false,
194 });
195 resolved.push(d);
196 }
197 }
198 for id in &t.depends_on {
199 if !seen.insert(id.as_str()) {
200 continue;
201 }
202 match index.get(id.as_str()) {
203 Some(&d) => resolved.push(d),
204 None => diags.push(
205 Diagnostic::new(
206 Severity::Error,
207 "graph.dangling",
208 format!("{} depends on {id}, which does not exist", t.id),
209 )
210 .at(&parsed.path)
211 .line(t.line)
212 .hint("fix the task ID or remove the reference"),
213 ),
214 }
215 deps.push(Dependency {
216 id: id.clone(),
217 kind: DependencyKind::Explicit,
218 missing: !index.contains_key(id.as_str()),
219 });
220 }
221 direct.push(deps);
222 edges.push(resolved);
223 }
224
225 let component = strongly_connected(&edges);
227 let mut members: HashMap<usize, Vec<usize>> = HashMap::new();
228 for (i, &c) in component.iter().enumerate() {
229 members.entry(c).or_default().push(i);
230 }
231 let in_cycle = |i: usize| members[&component[i]].len() > 1 || edges[i].contains(&i);
232 let mut reported = BTreeSet::new();
233 for i in 0..tasks.len() {
234 if in_cycle(i) && reported.insert(component[i]) {
235 let ids: Vec<&str> = members[&component[i]]
236 .iter()
237 .map(|&m| tasks[m].id.as_str())
238 .collect();
239 diags.push(
240 Diagnostic::new(
241 Severity::Error,
242 "graph.cycle",
243 format!("dependency cycle: {}", ids.join(" → ")),
244 )
245 .at(&parsed.path)
246 .line(tasks[i].line)
247 .hint("remove one of the `depends on` references"),
248 );
249 }
250 }
251
252 let mut out = Vec::with_capacity(tasks.len());
254 let mut totals = ScheduleTotals::default();
255 for (i, t) in tasks.iter().enumerate() {
256 let mut blockers: Vec<(usize, String)> = Vec::new();
257 for (dep, &d) in direct[i]
258 .iter()
259 .zip(resolved_or_missing(&direct[i], &index).iter())
260 {
261 match d {
262 None => blockers.push((usize::MAX, dep.id.clone())),
263 Some(d) => {
264 let cyclic = in_cycle(i) && component[d] == component[i];
265 if !tasks[d].done || cyclic {
266 blockers.push((d, dep.id.clone()));
267 }
268 }
269 }
270 }
271 blockers.sort();
272 blockers.dedup();
273 let state = if t.done {
274 totals.done += 1;
275 TaskState::Done
276 } else if blockers.is_empty() && !in_cycle(i) {
277 totals.ready += 1;
278 TaskState::Ready
279 } else {
280 totals.blocked += 1;
281 TaskState::Blocked
282 };
283 out.push(ScheduledTask {
284 id: t.id.clone(),
285 state,
286 depends_on: direct[i].clone(),
287 blocked_by: if t.done {
288 Vec::new()
289 } else {
290 blockers.into_iter().map(|(_, id)| id).collect()
291 },
292 });
293 }
294 (Schedule { tasks: out, totals }, diags)
295}
296
297fn resolved_or_missing(deps: &[Dependency], index: &HashMap<&str, usize>) -> Vec<Option<usize>> {
298 deps.iter()
299 .map(|d| index.get(d.id.as_str()).copied())
300 .collect()
301}
302
303fn strongly_connected(edges: &[Vec<usize>]) -> Vec<usize> {
305 const UNSEEN: usize = usize::MAX;
306 let n = edges.len();
307 let mut order = vec![UNSEEN; n];
308 let mut low = vec![0; n];
309 let mut on_stack = vec![false; n];
310 let mut component = vec![UNSEEN; n];
311 let mut stack = Vec::new();
312 let mut next_order = 0;
313 let mut next_component = 0;
314
315 for root in 0..n {
316 if order[root] != UNSEEN {
317 continue;
318 }
319 let mut work = vec![(root, 0usize)];
321 while let Some(&mut (v, ref mut e)) = work.last_mut() {
322 if *e == 0 && order[v] == UNSEEN {
323 order[v] = next_order;
324 low[v] = next_order;
325 next_order += 1;
326 stack.push(v);
327 on_stack[v] = true;
328 }
329 if let Some(&w) = edges[v].get(*e) {
330 *e += 1;
331 if order[w] == UNSEEN {
332 work.push((w, 0));
333 } else if on_stack[w] {
334 low[v] = low[v].min(order[w]);
335 }
336 continue;
337 }
338 work.pop();
339 if let Some(&(parent, _)) = work.last() {
340 low[parent] = low[parent].min(low[v]);
341 }
342 if low[v] == order[v] {
343 while let Some(w) = stack.pop() {
344 on_stack[w] = false;
345 component[w] = next_component;
346 if w == v {
347 break;
348 }
349 }
350 next_component += 1;
351 }
352 }
353 }
354 component
355}
356
357#[must_use]
360pub fn dependents(schedule: &Schedule, id: &str) -> Vec<String> {
361 let mut waiting: BTreeSet<&str> = BTreeSet::from([id]);
362 loop {
363 let before = waiting.len();
364 for t in &schedule.tasks {
365 if t.state != TaskState::Done
366 && t.depends_on.iter().any(|d| waiting.contains(d.id.as_str()))
367 {
368 waiting.insert(t.id.as_str());
369 }
370 }
371 if waiting.len() == before {
372 break;
373 }
374 }
375 schedule
376 .tasks
377 .iter()
378 .filter(|t| t.id != id && waiting.contains(t.id.as_str()))
379 .map(|t| t.id.clone())
380 .collect()
381}
382
383#[cfg(test)]
384mod tests {
385 use super::*;
386 use crate::snapshot::Totals;
387
388 type Spec<'a> = (
390 &'a str,
391 &'a str,
392 Option<&'a str>,
393 bool,
394 Option<&'a str>,
395 bool,
396 &'a [&'a str],
397 );
398
399 fn parsed(spec: &[Spec<'_>]) -> ParsedTasks {
400 parsed_in(DependencyMode::Structural, spec)
401 }
402
403 fn parsed_in(dependency_mode: DependencyMode, spec: &[Spec<'_>]) -> ParsedTasks {
404 let tasks: Vec<Task> = spec
405 .iter()
406 .enumerate()
407 .map(|(n, &(id, phase, sub, parallel, story, done, deps))| Task {
408 id: id.to_owned(),
409 done,
410 parallel,
411 story: story.map(str::to_owned),
412 yours: false,
413 title: String::new(),
414 depends_on: deps.iter().map(|d| (*d).to_owned()).collect(),
415 phase: Some(phase.to_owned()),
416 subsection: sub.map(str::to_owned),
417 line: u32::try_from(n + 1).unwrap(),
418 byte_range: [0, 0],
419 line_hash: String::new(),
420 })
421 .collect();
422 ParsedTasks {
423 path: "tasks.md".to_owned(),
424 phases: Vec::new(),
425 totals: Totals::default(),
426 tasks,
427 dependency_mode,
428 }
429 }
430
431 fn states(s: &Schedule) -> Vec<(&str, TaskState, Vec<&str>)> {
432 s.tasks
433 .iter()
434 .map(|t| {
435 (
436 t.id.as_str(),
437 t.state,
438 t.blocked_by.iter().map(String::as_str).collect(),
439 )
440 })
441 .collect()
442 }
443
444 use TaskState::{Blocked, Done, Ready};
445
446 const SETUP: &str = "Phase 1: Setup";
447 const FOUND: &str = "Phase 2: Foundational";
448 const US1: &str = "Phase 3: User Story 1 - A";
449 const US2: &str = "Phase 4: User Story 2 - B";
450 const POLISH: &str = "Phase 5: Polish & Cross-Cutting Concerns";
451
452 #[test]
453 fn classifies_spec_kit_headings() {
454 assert_eq!(
455 classify("Phase 1: Setup (Shared Infrastructure)", false),
456 PhaseKind::Setup
457 );
458 assert_eq!(
459 classify("Phase 2: Foundational (Blocking Prerequisites)", false),
460 PhaseKind::Foundational
461 );
462 assert_eq!(
463 classify("Phase 3: User Story 1 - Login (Priority: P1) 🎯 MVP", false),
464 PhaseKind::Story
465 );
466 assert_eq!(
467 classify("Phase 9: Polish & Cross-Cutting Concerns", false),
468 PhaseKind::Polish
469 );
470 assert_eq!(
471 classify("Phase 10: Convergence", false),
472 PhaseKind::Convergence
473 );
474 assert_eq!(classify("Phase 4: Login", true), PhaseKind::Story);
475 assert_eq!(classify("User stories overview", false), PhaseKind::Other);
476 }
477
478 #[test]
479 fn open_setup_blocks_everything_after_it() {
480 let p = parsed(&[
481 ("T001", SETUP, None, false, None, false, &[]),
482 ("T002", FOUND, None, false, None, false, &[]),
483 ("T003", US1, None, false, Some("US1"), false, &[]),
484 ]);
485 let (s, d) = schedule(&p);
486 assert!(d.is_empty());
487 assert_eq!(
488 states(&s),
489 [
490 ("T001", Ready, vec![]),
491 ("T002", Blocked, vec!["T001"]),
492 ("T003", Blocked, vec!["T001", "T002"]),
493 ]
494 );
495 }
496
497 #[test]
498 fn a_skipped_task_names_what_waits_on_it() {
499 let p = parsed(&[
500 ("T001", SETUP, None, false, None, false, &[]),
501 ("T002", FOUND, None, false, None, false, &[]),
502 ("T003", US1, None, false, Some("US1"), false, &[]),
503 ]);
504 let (s, _) = schedule(&p);
505 assert_eq!(dependents(&s, "T001"), ["T002", "T003"]);
506 assert_eq!(dependents(&s, "T002"), ["T003"]);
507 assert!(dependents(&s, "T003").is_empty());
508 }
509
510 #[test]
511 fn stories_are_independent_and_polish_waits_for_all() {
512 let p = parsed(&[
513 ("T001", SETUP, None, false, None, true, &[]),
514 ("T002", FOUND, None, false, None, true, &[]),
515 ("T003", US1, None, false, Some("US1"), false, &[]),
516 ("T004", US2, None, false, Some("US2"), false, &[]),
517 ("T005", POLISH, None, false, None, false, &[]),
518 ]);
519 let (s, _) = schedule(&p);
520 assert_eq!(
521 states(&s),
522 [
523 ("T001", Done, vec![]),
524 ("T002", Done, vec![]),
525 ("T003", Ready, vec![]),
526 ("T004", Ready, vec![]),
527 ("T005", Blocked, vec!["T003", "T004"]),
528 ]
529 );
530 assert_eq!(
531 s.totals,
532 ScheduleTotals {
533 done: 2,
534 ready: 2,
535 blocked: 1
536 }
537 );
538 }
539
540 #[test]
541 fn parallel_runs_fork_and_join() {
542 let p = parsed(&[
543 ("T001", SETUP, None, false, None, true, &[]),
544 ("T002", SETUP, None, true, None, false, &[]),
545 ("T003", SETUP, None, true, None, false, &[]),
546 ("T004", SETUP, None, false, None, false, &[]),
547 ]);
548 let (s, _) = schedule(&p);
549 assert_eq!(
550 states(&s),
551 [
552 ("T001", Done, vec![]),
553 ("T002", Ready, vec![]),
554 ("T003", Ready, vec![]),
555 ("T004", Blocked, vec!["T002", "T003"]),
556 ]
557 );
558 }
559
560 #[test]
561 fn tests_subsection_comes_before_implementation() {
562 let p = parsed(&[
563 (
564 "T001",
565 US1,
566 Some("Tests for User Story 1"),
567 true,
568 Some("US1"),
569 false,
570 &[],
571 ),
572 (
573 "T002",
574 US1,
575 Some("Implementation for User Story 1"),
576 true,
577 Some("US1"),
578 false,
579 &[],
580 ),
581 ]);
582 let (s, _) = schedule(&p);
583 assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
584 }
585
586 #[test]
587 fn explicit_dependency_crosses_stories() {
588 let p = parsed(&[
589 ("T001", US1, None, false, Some("US1"), false, &[]),
590 ("T002", US2, None, false, Some("US2"), false, &["T001"]),
591 ]);
592 let (s, _) = schedule(&p);
593 assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
594 assert_eq!(s.tasks[1].depends_on[0].kind, DependencyKind::Explicit);
595 }
596
597 #[test]
598 fn declared_mode_keeps_phase_order_but_drops_structure_within_a_phase() {
599 let p = parsed_in(
600 DependencyMode::Declared,
601 &[
602 ("T001", SETUP, None, false, None, true, &[]),
603 ("T002", SETUP, None, false, None, false, &["T001"]),
604 ("T003", SETUP, None, true, None, false, &["T001"]),
605 (
606 "T004",
607 US1,
608 Some("Tests"),
609 true,
610 Some("US1"),
611 false,
612 &["T002"],
613 ),
614 (
615 "T005",
616 US1,
617 Some("Implementation"),
618 true,
619 Some("US1"),
620 false,
621 &[],
622 ),
623 ],
624 );
625 let (s, d) = schedule(&p);
626 assert!(d.is_empty());
627 assert_eq!(
628 states(&s),
629 [
630 ("T001", Done, vec![]),
631 ("T002", Ready, vec![]),
632 ("T003", Ready, vec![]),
633 ("T004", Blocked, vec!["T002", "T003"]),
634 ("T005", Blocked, vec!["T002", "T003"]),
635 ]
636 );
637 }
638
639 #[test]
640 fn dangling_reference_is_an_error_and_blocks() {
641 let p = parsed(&[("T001", SETUP, None, false, None, false, &["T099"])]);
642 let (s, d) = schedule(&p);
643 assert_eq!(d[0].code, "graph.dangling");
644 assert_eq!(d[0].line, Some(1));
645 assert_eq!(states(&s)[0], ("T001", Blocked, vec!["T099"]));
646 assert!(s.tasks[0].depends_on[0].missing);
647 }
648
649 #[test]
650 fn cycles_and_self_references_are_errors_and_never_ready() {
651 let p = parsed(&[
653 ("T001", SETUP, None, false, None, false, &["T002"]),
654 ("T002", SETUP, None, false, None, true, &[]),
655 ("T003", POLISH, None, false, None, false, &["T003"]),
656 ]);
657 let (s, d) = schedule(&p);
658 let codes: Vec<_> = d
659 .iter()
660 .map(|d| (d.code.as_str(), d.message.as_str()))
661 .collect();
662 assert_eq!(
663 codes,
664 [
665 ("graph.cycle", "dependency cycle: T001 → T002"),
666 ("graph.cycle", "dependency cycle: T003"),
667 ]
668 );
669 assert_eq!(s.tasks[0].state, Blocked);
670 assert_eq!(s.tasks[2].state, Blocked);
671 }
672
673 mod properties {
674 use super::*;
675 use proptest::prelude::*;
676
677 type OwnedSpec = (
679 String,
680 &'static str,
681 Option<String>,
682 bool,
683 Option<&'static str>,
684 bool,
685 Vec<String>,
686 );
687
688 const PHASES: [&str; 6] = [SETUP, FOUND, US1, US2, "Phase 6: Story notes", POLISH];
689
690 fn task_lists() -> impl Strategy<Value = ParsedTasks> {
693 prop::collection::vec(
694 (
695 0..PHASES.len(),
696 0..3usize,
697 any::<bool>(),
698 any::<bool>(),
699 prop::option::of(0..64usize),
700 ),
701 1..40,
702 )
703 .prop_map(|mut rows| {
704 rows.sort_by_key(|r| (r.0, r.1));
705 let ids: Vec<String> = (1..=rows.len()).map(|n| format!("T{n:03}")).collect();
706 let spec: Vec<OwnedSpec> = rows
707 .iter()
708 .enumerate()
709 .map(|(i, &(ph, sub, par, done, back))| {
710 let story = match ph {
711 2 => Some("US1"),
712 3 => Some("US2"),
713 _ => None,
714 };
715 let deps = back
716 .filter(|_| i > 0)
717 .map(|b| vec![ids[b % i].clone()])
718 .unwrap_or_default();
719 (
720 ids[i].clone(),
721 PHASES[ph],
722 Some(format!("S{sub}")),
723 par,
724 story,
725 done,
726 deps,
727 )
728 })
729 .collect();
730 let owned: Vec<Vec<&str>> = spec
731 .iter()
732 .map(|r| r.6.iter().map(String::as_str).collect())
733 .collect();
734 let rows: Vec<Spec<'_>> = spec
735 .iter()
736 .zip(&owned)
737 .map(|(r, d)| {
738 (
739 r.0.as_str(),
740 r.1,
741 r.2.as_deref(),
742 r.3,
743 r.4,
744 r.5,
745 d.as_slice(),
746 )
747 })
748 .collect();
749 parsed(&rows)
750 })
751 }
752
753 proptest! {
754 #[test]
755 fn ready_means_every_dependency_is_done(p in task_lists()) {
756 let (s, _) = schedule(&p);
757 let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
758 for t in &s.tasks {
759 if t.state == Ready {
760 prop_assert!(t.depends_on.iter().all(|d| done[d.id.as_str()]));
761 }
762 }
763 }
764
765 #[test]
766 fn open_tasks_with_done_dependencies_are_ready(p in task_lists()) {
767 let (s, _) = schedule(&p);
768 let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
769 for (t, task) in s.tasks.iter().zip(&p.tasks) {
770 if !task.done && t.depends_on.iter().all(|d| done[d.id.as_str()]) {
771 prop_assert_eq!(t.state, Ready);
772 }
773 }
774 }
775
776 #[test]
777 fn stories_never_depend_structurally_on_each_other(p in task_lists()) {
778 let (s, _) = schedule(&p);
779 let story: HashMap<&str, Option<&str>> =
780 p.tasks.iter().map(|t| (t.id.as_str(), t.story.as_deref())).collect();
781 for t in &s.tasks {
782 for d in t.depends_on.iter().filter(|d| d.kind == DependencyKind::Structural) {
783 if let (Some(a), Some(b)) = (story[t.id.as_str()], story[d.id.as_str()]) {
784 prop_assert_eq!(a, b);
785 }
786 }
787 }
788 }
789
790 #[test]
791 fn backward_references_never_create_cycles(p in task_lists()) {
792 let (s, d) = schedule(&p);
793 prop_assert!(d.is_empty(), "{:?}", d);
794 prop_assert_eq!(s.totals.done + s.totals.ready + s.totals.blocked, p.tasks.len());
795 }
796 }
797 }
798}