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 scenarios: Vec::new(),
416 phase: Some(phase.to_owned()),
417 subsection: sub.map(str::to_owned),
418 line: u32::try_from(n + 1).unwrap(),
419 byte_range: [0, 0],
420 line_hash: String::new(),
421 })
422 .collect();
423 ParsedTasks {
424 path: "tasks.md".to_owned(),
425 phases: Vec::new(),
426 totals: Totals::default(),
427 tasks,
428 dependency_mode,
429 }
430 }
431
432 fn states(s: &Schedule) -> Vec<(&str, TaskState, Vec<&str>)> {
433 s.tasks
434 .iter()
435 .map(|t| {
436 (
437 t.id.as_str(),
438 t.state,
439 t.blocked_by.iter().map(String::as_str).collect(),
440 )
441 })
442 .collect()
443 }
444
445 use TaskState::{Blocked, Done, Ready};
446
447 const SETUP: &str = "Phase 1: Setup";
448 const FOUND: &str = "Phase 2: Foundational";
449 const US1: &str = "Phase 3: User Story 1 - A";
450 const US2: &str = "Phase 4: User Story 2 - B";
451 const POLISH: &str = "Phase 5: Polish & Cross-Cutting Concerns";
452
453 #[test]
454 fn classifies_spec_kit_headings() {
455 assert_eq!(
456 classify("Phase 1: Setup (Shared Infrastructure)", false),
457 PhaseKind::Setup
458 );
459 assert_eq!(
460 classify("Phase 2: Foundational (Blocking Prerequisites)", false),
461 PhaseKind::Foundational
462 );
463 assert_eq!(
464 classify("Phase 3: User Story 1 - Login (Priority: P1) 🎯 MVP", false),
465 PhaseKind::Story
466 );
467 assert_eq!(
468 classify("Phase 9: Polish & Cross-Cutting Concerns", false),
469 PhaseKind::Polish
470 );
471 assert_eq!(
472 classify("Phase 10: Convergence", false),
473 PhaseKind::Convergence
474 );
475 assert_eq!(classify("Phase 4: Login", true), PhaseKind::Story);
476 assert_eq!(classify("User stories overview", false), PhaseKind::Other);
477 }
478
479 #[test]
480 fn open_setup_blocks_everything_after_it() {
481 let p = parsed(&[
482 ("T001", SETUP, None, false, None, false, &[]),
483 ("T002", FOUND, None, false, None, false, &[]),
484 ("T003", US1, None, false, Some("US1"), false, &[]),
485 ]);
486 let (s, d) = schedule(&p);
487 assert!(d.is_empty());
488 assert_eq!(
489 states(&s),
490 [
491 ("T001", Ready, vec![]),
492 ("T002", Blocked, vec!["T001"]),
493 ("T003", Blocked, vec!["T001", "T002"]),
494 ]
495 );
496 }
497
498 #[test]
499 fn a_skipped_task_names_what_waits_on_it() {
500 let p = parsed(&[
501 ("T001", SETUP, None, false, None, false, &[]),
502 ("T002", FOUND, None, false, None, false, &[]),
503 ("T003", US1, None, false, Some("US1"), false, &[]),
504 ]);
505 let (s, _) = schedule(&p);
506 assert_eq!(dependents(&s, "T001"), ["T002", "T003"]);
507 assert_eq!(dependents(&s, "T002"), ["T003"]);
508 assert!(dependents(&s, "T003").is_empty());
509 }
510
511 #[test]
512 fn stories_are_independent_and_polish_waits_for_all() {
513 let p = parsed(&[
514 ("T001", SETUP, None, false, None, true, &[]),
515 ("T002", FOUND, None, false, None, true, &[]),
516 ("T003", US1, None, false, Some("US1"), false, &[]),
517 ("T004", US2, None, false, Some("US2"), false, &[]),
518 ("T005", POLISH, None, false, None, false, &[]),
519 ]);
520 let (s, _) = schedule(&p);
521 assert_eq!(
522 states(&s),
523 [
524 ("T001", Done, vec![]),
525 ("T002", Done, vec![]),
526 ("T003", Ready, vec![]),
527 ("T004", Ready, vec![]),
528 ("T005", Blocked, vec!["T003", "T004"]),
529 ]
530 );
531 assert_eq!(
532 s.totals,
533 ScheduleTotals {
534 done: 2,
535 ready: 2,
536 blocked: 1
537 }
538 );
539 }
540
541 #[test]
542 fn parallel_runs_fork_and_join() {
543 let p = parsed(&[
544 ("T001", SETUP, None, false, None, true, &[]),
545 ("T002", SETUP, None, true, None, false, &[]),
546 ("T003", SETUP, None, true, None, false, &[]),
547 ("T004", SETUP, None, false, None, false, &[]),
548 ]);
549 let (s, _) = schedule(&p);
550 assert_eq!(
551 states(&s),
552 [
553 ("T001", Done, vec![]),
554 ("T002", Ready, vec![]),
555 ("T003", Ready, vec![]),
556 ("T004", Blocked, vec!["T002", "T003"]),
557 ]
558 );
559 }
560
561 #[test]
562 fn tests_subsection_comes_before_implementation() {
563 let p = parsed(&[
564 (
565 "T001",
566 US1,
567 Some("Tests for User Story 1"),
568 true,
569 Some("US1"),
570 false,
571 &[],
572 ),
573 (
574 "T002",
575 US1,
576 Some("Implementation for User Story 1"),
577 true,
578 Some("US1"),
579 false,
580 &[],
581 ),
582 ]);
583 let (s, _) = schedule(&p);
584 assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
585 }
586
587 #[test]
588 fn explicit_dependency_crosses_stories() {
589 let p = parsed(&[
590 ("T001", US1, None, false, Some("US1"), false, &[]),
591 ("T002", US2, None, false, Some("US2"), false, &["T001"]),
592 ]);
593 let (s, _) = schedule(&p);
594 assert_eq!(states(&s)[1], ("T002", Blocked, vec!["T001"]));
595 assert_eq!(s.tasks[1].depends_on[0].kind, DependencyKind::Explicit);
596 }
597
598 #[test]
599 fn declared_mode_keeps_phase_order_but_drops_structure_within_a_phase() {
600 let p = parsed_in(
601 DependencyMode::Declared,
602 &[
603 ("T001", SETUP, None, false, None, true, &[]),
604 ("T002", SETUP, None, false, None, false, &["T001"]),
605 ("T003", SETUP, None, true, None, false, &["T001"]),
606 (
607 "T004",
608 US1,
609 Some("Tests"),
610 true,
611 Some("US1"),
612 false,
613 &["T002"],
614 ),
615 (
616 "T005",
617 US1,
618 Some("Implementation"),
619 true,
620 Some("US1"),
621 false,
622 &[],
623 ),
624 ],
625 );
626 let (s, d) = schedule(&p);
627 assert!(d.is_empty());
628 assert_eq!(
629 states(&s),
630 [
631 ("T001", Done, vec![]),
632 ("T002", Ready, vec![]),
633 ("T003", Ready, vec![]),
634 ("T004", Blocked, vec!["T002", "T003"]),
635 ("T005", Blocked, vec!["T002", "T003"]),
636 ]
637 );
638 }
639
640 #[test]
641 fn dangling_reference_is_an_error_and_blocks() {
642 let p = parsed(&[("T001", SETUP, None, false, None, false, &["T099"])]);
643 let (s, d) = schedule(&p);
644 assert_eq!(d[0].code, "graph.dangling");
645 assert_eq!(d[0].line, Some(1));
646 assert_eq!(states(&s)[0], ("T001", Blocked, vec!["T099"]));
647 assert!(s.tasks[0].depends_on[0].missing);
648 }
649
650 #[test]
651 fn cycles_and_self_references_are_errors_and_never_ready() {
652 let p = parsed(&[
654 ("T001", SETUP, None, false, None, false, &["T002"]),
655 ("T002", SETUP, None, false, None, true, &[]),
656 ("T003", POLISH, None, false, None, false, &["T003"]),
657 ]);
658 let (s, d) = schedule(&p);
659 let codes: Vec<_> = d
660 .iter()
661 .map(|d| (d.code.as_str(), d.message.as_str()))
662 .collect();
663 assert_eq!(
664 codes,
665 [
666 ("graph.cycle", "dependency cycle: T001 → T002"),
667 ("graph.cycle", "dependency cycle: T003"),
668 ]
669 );
670 assert_eq!(s.tasks[0].state, Blocked);
671 assert_eq!(s.tasks[2].state, Blocked);
672 }
673
674 mod properties {
675 use super::*;
676 use proptest::prelude::*;
677
678 type OwnedSpec = (
680 String,
681 &'static str,
682 Option<String>,
683 bool,
684 Option<&'static str>,
685 bool,
686 Vec<String>,
687 );
688
689 const PHASES: [&str; 6] = [SETUP, FOUND, US1, US2, "Phase 6: Story notes", POLISH];
690
691 fn task_lists() -> impl Strategy<Value = ParsedTasks> {
694 prop::collection::vec(
695 (
696 0..PHASES.len(),
697 0..3usize,
698 any::<bool>(),
699 any::<bool>(),
700 prop::option::of(0..64usize),
701 ),
702 1..40,
703 )
704 .prop_map(|mut rows| {
705 rows.sort_by_key(|r| (r.0, r.1));
706 let ids: Vec<String> = (1..=rows.len()).map(|n| format!("T{n:03}")).collect();
707 let spec: Vec<OwnedSpec> = rows
708 .iter()
709 .enumerate()
710 .map(|(i, &(ph, sub, par, done, back))| {
711 let story = match ph {
712 2 => Some("US1"),
713 3 => Some("US2"),
714 _ => None,
715 };
716 let deps = back
717 .filter(|_| i > 0)
718 .map(|b| vec![ids[b % i].clone()])
719 .unwrap_or_default();
720 (
721 ids[i].clone(),
722 PHASES[ph],
723 Some(format!("S{sub}")),
724 par,
725 story,
726 done,
727 deps,
728 )
729 })
730 .collect();
731 let owned: Vec<Vec<&str>> = spec
732 .iter()
733 .map(|r| r.6.iter().map(String::as_str).collect())
734 .collect();
735 let rows: Vec<Spec<'_>> = spec
736 .iter()
737 .zip(&owned)
738 .map(|(r, d)| {
739 (
740 r.0.as_str(),
741 r.1,
742 r.2.as_deref(),
743 r.3,
744 r.4,
745 r.5,
746 d.as_slice(),
747 )
748 })
749 .collect();
750 parsed(&rows)
751 })
752 }
753
754 proptest! {
755 #[test]
756 fn ready_means_every_dependency_is_done(p in task_lists()) {
757 let (s, _) = schedule(&p);
758 let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
759 for t in &s.tasks {
760 if t.state == Ready {
761 prop_assert!(t.depends_on.iter().all(|d| done[d.id.as_str()]));
762 }
763 }
764 }
765
766 #[test]
767 fn open_tasks_with_done_dependencies_are_ready(p in task_lists()) {
768 let (s, _) = schedule(&p);
769 let done: HashMap<&str, bool> = p.tasks.iter().map(|t| (t.id.as_str(), t.done)).collect();
770 for (t, task) in s.tasks.iter().zip(&p.tasks) {
771 if !task.done && t.depends_on.iter().all(|d| done[d.id.as_str()]) {
772 prop_assert_eq!(t.state, Ready);
773 }
774 }
775 }
776
777 #[test]
778 fn stories_never_depend_structurally_on_each_other(p in task_lists()) {
779 let (s, _) = schedule(&p);
780 let story: HashMap<&str, Option<&str>> =
781 p.tasks.iter().map(|t| (t.id.as_str(), t.story.as_deref())).collect();
782 for t in &s.tasks {
783 for d in t.depends_on.iter().filter(|d| d.kind == DependencyKind::Structural) {
784 if let (Some(a), Some(b)) = (story[t.id.as_str()], story[d.id.as_str()]) {
785 prop_assert_eq!(a, b);
786 }
787 }
788 }
789 }
790
791 #[test]
792 fn backward_references_never_create_cycles(p in task_lists()) {
793 let (s, d) = schedule(&p);
794 prop_assert!(d.is_empty(), "{:?}", d);
795 prop_assert_eq!(s.totals.done + s.totals.ready + s.totals.blocked, p.tasks.len());
796 }
797 }
798 }
799}